oj.uz

Submission #533172

# Submission time Handle Problem Language Result Execution time Memory
533172 2022-03-05T04:25:27 Z huangqr Aliens (IOI07_aliens) C++14
100 / 100
 3 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
const ll lim=2e5+5;
map<pl,bool>m;
ll n;

inline bool query(ll x,ll y){
	if(x>n||y>n||x<1||y<1)return false;
	if(m.find(make_pair(x,y))!=m.end())return m[make_pair(x,y)];
	cout<<"examine "<<x<<" "<<y<<"\n";
	cout.flush();
	string s;
	cin>>s;
	return m[make_pair(x,y)]=(s=="true");
}

int main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL);
	ll x,y;
	cin>>n>>x>>y;
	int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
	ll dist[4]={n-x,x-1,n-y,y-1},tsa[4];
	for(int i=0;i<4;i++){
		ll left = 0, right = dist[i], best = 0; //Binary search for the largest value that is red. Some modifications due to checkerboard 
		bool vroomed=0;
		while(left<=right){
			ll mid = (left+right)/2;
			if(query(x + mid * dx[i], y + mid * dy[i])){
				if(vroomed){
					best = max(best, mid);
					left = mid + 1;
				}
				else{
					vroomed = true;
					mid /= 2;
					while(mid){
						if(!query(x + mid * dx[i], y + mid * dy[i]))right = mid - 1;
						mid /= 2;
					}
				}
			}
			else{
				right = mid - 1;
			}
			if(i<2)tsa[i]=x+dx[i]*best;
			else tsa[i]=y+dy[i]*best;
		}
	}
	//cout<<"\n\n";
	//for(int i=0;i<4;i++)cout<<tsa[i]<<" ";
	assert(tsa[1]-tsa[0]==tsa[3]-tsa[2]);
	ll d=abs(tsa[1]-tsa[0])+1;
	x = (tsa[0]+tsa[1])/2, y = (tsa[2]+tsa[3])/2;
	//cout<<"centered xy:"<<x<<" "<<y<<"\n";
	while(query(x+2*d,y))x+=2*d;
	while(query(x,y+2*d))y+=2*d;
	//cout<<"presol:"<<x<<" "<<y<<"\n";
	if(!query(x+d,y+d))x-=d,y-=d;
	x-=d,y-=d;
	cout<<"solution "<<x<<" "<<y<<"\n";
	cout.flush();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 3 ms 308 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Output is correct
2 Correct 2 ms 200 KB Output is correct
3 Correct 2 ms 312 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 308 KB Output is correct