Submission #533172

#	Time	Username	Problem	Language	Result	Execution time	Memory
533172		huangqr	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	332 KiB

aliens

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10