And then my E got uphacked :) So i should feel lucky instead of regret now!

Good contest, enjoy it very much. E is brillant(it takes me the longest time to come up with the solution). F is interesting. However I found G much easier(n logn sqrtn with small constant, not standard solution, which got accepted soon after system test) but I was too sleepy to impletement it correctly in the last 15 minutes and successfully missed my LGM.

I can't wait to see cnnfls_csy reach 3500!

Well I understand the tutorial. Both of them are correct.

Hey, am I misunderstanding the tutorial for 1E? Shouldn't it be the case that $$$k\in [p, p + 30]\cup [q - 30, q]$$$, where $$$p$$$ is the first position that $$$a_{p + 1} - a_p > 0$$$, and $$$q$$$ is the last position that $$$a_{q + 1} - a_q > 0$$$?

cnnfls_csy will win IOI2023!

The first time that I realize the importance of a nice room.

For Div.1 D, the editorial said

It can be shown that in the optimal answer we use no more than one operation with each sunbed.

I'm curious about how to prove it.

Yes, consider a chain.

Seriously, I've never seen a problem more stupid than Div.1 E.

Div.1 C is weird. I dislike it very much.

It's not that I failed to solve it, but such problem should appear in MO instead of competitive programming.

lol, count me in.

Totally agree! I made lots of guesses when solving problem B, D, E and F.

It's like, intuition tells me this algorithm is right, so I write it down.

F is really awesome!

For each distinct value $$$x$$$, we need to consider every $$$cnt_y\leq cnt_x$$$. There are at most $$$cnt_x$$$ such $$$cnt_y$$$, so in total the complexity is $$$\sum cnt_x$$$.

It doesn't matter how many distinct $$$x$$$ there are, because we only need to consider $$$\sum cnt_x$$$, which is $$$n$$$.

because $$$n = \sum cnt_x$$$, and the pairs are unordered, which means we can simply iterate over all $$$cnt_y \leq cnt_x$$$ for better complexity

endl is too slow, use '\n' instead if you want to send wishes :)

First we can rotate the plane to make sure the center is above the x-axis and the circle doesn't cross the third quadrant. Next I use binary search to find two rays $$$a:(0,0)\to (x_1,y_1)$$$ and $$$b:(0,0)\to (x_2,y_2)$$$ that are almost tangential to the circle.

Then I enumerate all possible radius $$$r$$$（$$$r$$$ is an integer not greater than $$$10^5$$$ so it's ok to do so）。With the distance between $$$a$$$ and the circle (let's call it $$$d_1$$$) and it's radius $$$r$$$ we can work out the coordinate of the center $$$(x,y)$$$ (with some senior high school geometry). I also make sure that $$$(x_1,y_1)$$$ lies in the second quadrant and is as close to the circle as possible (so if the circle doesn't cross the second quadrant, what I will get is $$$x_1=-1$$$ and $$$y_1=10^5$$$). Because of the constraints above (the bolded part) we can see that $$$d_1$$$ is always useful information (which means that $$$d_1$$$ is not $$$\mathrm{distance}((x,y),(0,0))-r$$$, this infomation is useless because it's too easy to get and we can't fix $$$(x,y)$$$ simply with $$$r$$$ and $$$\mathrm{distance}((x,y),(0,0))-r$$$ : we need more infomation : $$$d_1$$$)

After fixing $$$(x,y)$$$ we have the whole circle, so we can calculate the distance between the circle and $$$b$$$, and check whether it is equal to what the interactor outputs. If yes, then $$$(x,y,r)$$$ is the answer, otherwise go through other radii until we find out the answer.

#include <bits/stdc++.h>
 
#define db double
#define ll long long
#define ld long double
#define ull unsigned long long
#define vint vector <int>
#define vpii vector <pii>
 
#define pii pair <int,int>
#define fi first
#define se second
#define pb emplace_back
#define mem(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
 
inline int read(){
	int x=0; char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=x*10+s-'0',s=getchar();
	return x;
}
 
const ld eps=1e-6;
const ll N=2e5;
 
ld max(ld x,ld y){return x>y?x:y;}
ld min(ld x,ld y){return x<y?x:y;}
bool Eq(ld x,ld y){return fabs(x-y)<eps;}
bool Isz(ld x){return fabs(x)<eps;}
 
ld up,down,left,right;
ld dis(ld x1,ld y1,ld x2,ld y2){return sqrt((x1-x2)*(x1-x2)+((y1-y2)*(y1-y2)));}
ld dis(ld x1,ld y1,ld x2,ld y2,ld r){
	ld dot=x1*x2+y1*y2,d=dis(0,0,x2,y2);
	if(dot<eps)return max((ld)0,d-r);
	ld nd=dot/dis(0,0,x1,y1);
	return max((ld)0,sqrt(d*d-nd*nd)-r);
}
 
int swp,type;
void ref(int &x,int &y){int t=y; y=x,x=-t;} // counterclockwise rotate
ld query(int x,int y){
	for(int j=1;j<=swp;j++)ref(x,y);
	std::cout<<"? "<<x<<" "<<y<<std::endl;
	ld res; std::cin>>res; return res;
}
void answ(int x,int y,int r){
	for(int j=1;j<=swp;j++)ref(x,y);
	std::cout<<"! "<<x<<" "<<y<<" "<<r<<std::endl,exit(0);
}
void answer(ld x,ld y,ld r){
	int xx=x<0?x-eps:x+eps,yy=y<0?y-eps:y+eps;
	return answ(xx,yy,r+eps);
}
 
int main(){
	up=query(0,10),down=query(0,-10),left=query(-10,0),right=query(10,0);
	type=Isz(up)+Isz(down)+Isz(left)+Isz(right);
	if(type==0){
		ld mx=max(max(up,down),max(left,right));
		if(down==mx&&right==mx)swp=1;
		if(right==mx&&up==mx)swp=2;
		if(up==mx&&left==mx)swp=3;
	}
	if(type==1){if(Isz(left))swp=1; if(Isz(down))swp=2; if(Isz(right))swp=3;}
	if(type==2){
		if(Isz(left)&&Isz(up))swp=1;
		if(Isz(down)&&Isz(left))swp=2;
		if(Isz(right)&&Isz(down))swp=3;
	}
	up=query(0,10),down=query(0,-10),left=query(-10,0),right=query(10,0);
	
	int l=1,r=N*2-1,xx,yy,tx,ty; ld res;
	while(l<r){
		int m=l+r>>1;
		xx=-min(N,m),yy=N-max(0,m-N);
		(res=query(xx,yy))>1e-6?r=m:l=m+1;
	} xx=-min(N,l),yy=N-max(0,l-N);
	ld upl=query(tx,ty); ref(tx,ty),ref(tx,ty);
	ld downr=query(tx,ty),mdis=std::min(upl,downr);
	
	int xx2,yy2; l=1,r=N*3-1;
	while(l<r){
		int m=(l+r>>1)+1;
		xx2=min(N,m),yy2=-N+max(0ll,m-N);
		(res=query(xx2,yy2)>1e-6)?l=m:r=m-1;
	} xx2=min(N,l),yy2=-N+max(0,l-N),res=query(xx2,yy2);
	
	for(int r=1;r<=1e5;r++){
		ld y=mdis+r,x=sqrt((down+r)*(down+r)-y*y);
		ll d=1ll*xx*xx+1ll*yy+yy;
		ld sn=(ld)fabs(yy)/(ld)(sqrt(d)); // rotate the plane by some angle
		ld cs=(ld)fabs(xx)/(ld)(sqrt(d));
		if(Eq(mdis,upl))x=-x;
		ld x0=x*cs+y*sn,y0=-x*sn+y*cs; x=x0,y=y0;
		if(Eq(res,dis(xx2,yy2,x,y,r)))answer(x,y,r);
	}
	return 0;
}

(I'm a Chinese student, sorry for my poor English.) I spent four hours on the problem (from 9:30 p.m. to 1:30 a.m!) so I don't have time to help my teammates lol

It's so ridiculous that my $$$a=5,b=4$$$ solution to div.1 A passed the previous pretests. The pretests are likely to be generated by the problem setter's feet I guess. I will think twice before participating in a Chinese round again (last time when I participated in a Chinese round I said so. My rating went down in every Chinese round before lol).

Thank you very much.

Well actually I did so, but there might be something wrong with my operation just now so that when I previewed the comment the symbol $$ didn't work.

Now it works. $$$\mathcal{O}(2^{n+2}n^2)$$$

Sad to see that simply changing long long into int can make a huge difference to not only the result but also my current rating, though my solution has a complexity of 2^nn^2 (actually it is 2^{n+2}n^2!).

TLE : 122856541

AC : 122887934

btw how to type LaTeX in Codeforces?

Well, I performed badly in the contest so I even had to say goodbye to the International Master. But after I discovered the secret of Div.1B, I thought the solution was really beautiful.

Actually, I got FST on B because there was a stupid bug in my code. (I fixed it after the contest and got AC) And my solution of C was close to the editorial but I didn't want to improve it anymore after that round was unrated.

Finally a Rated Div.1 contest！ I see many familiar faces！Hope everything goes well and I can realize my dream for this year — being a Grandmaster！（Actually, if the last Div.1 Round wasn't unrated, maybe I'm a Grandmaster now）

I am wondering too. The codestyles of his A&B&C are totally different.

Oh my god , is this round unrated ?

I'm a step away from the master .

I use randomize + greedy + soting and PASSED F!

This is my code

But I don't know how to solve it properly . I think I'm a little lucky

I want to become purple！I've been waiting for it for a long time!

Stop,you guys ! You are shaming our school !