Submission #79226

#	Time	Username	Problem	Language	Result	Execution time	Memory
79226		Plurm	Aliens (IOI07_aliens)	C++11	0 / 100	3 ms	628 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
enum dir{
	up, down, lleft, rright
};
int n;
const pair<long long,long long> NOPE = make_pair(-1,-1);
map<pair<long long,long long>,bool> mp;
bool query(long long x,long long y){
	if(x <= 0 || y <= 0 || x > n || y > n) return false;
	if(mp.find(make_pair(x,y)) != mp.end()) return mp[make_pair(x,y)];
	printf("examine %lld %lld\n",x,y);
	fflush(stdout);
	char in[8];
	scanf("%s",in);
	mp[make_pair(x,y)] = in[0] == 't';
	return in[0] == 't';
}
pair<long long,long long> search(long long x,long long y,dir d){
	int sstate = 0;
	if(d == up){
		for(long long i = 1; y+i <= (long long)n; i *= 2ll){
			if(query(x,y+i)){
				if(sstate == 1){
					return make_pair(x,y+i);
				}
			}else{
				if(sstate == 0) sstate = 1;
			}
		}
		return NOPE;
	}else if(d == down){
		for(long long i = 1; y-i > 0ll; i *= 2ll){
			if(query(x,y-i)){
				if(sstate == 1){
					return make_pair(x,y-i);
				}
			}else{
				if(sstate == 0) sstate = 1;
			}
		}
		return NOPE;
	}else if(d == lleft){
		for(long long i = 1; x-i > 0ll; i *= 2ll){
			if(query(x-i,y)){
				if(sstate == 1){
					return make_pair(x-i,y);
				}
			}else{
				if(sstate == 0) sstate = 1;
			}
		}
		return NOPE;
	}else{
		for(long long i = 1; x+i <= (long long)n; i *= 2ll){
			if(query(x+i,y)){
				if(sstate == 1){
					return make_pair(x+i,y);
				}
			}else{
				if(sstate == 0) sstate = 1;
			}
		}
		return NOPE;
	}
}
long long getsidelength(long long x,long long y){
	long long byu = -1ll;
	long long byd = -1ll;
	for(long long i = 1; ; i *= 2ll){
		if(!query(x,y+i)){
			long long hi = min(i,n-y);
			long long lo = 0ll;
			long long mid;
			while(lo < hi){
				mid = (lo + hi)/2ll;
				if(query(x,y+mid)){
					lo = mid+1ll;
				}else{
					hi = mid;
				}
			}
			byu = y+lo;
			break;
		}
	}
	for(long long i = 1; ; i *= 2ll){
		if(!query(x,y-i)){
			long long hi = min(i,y);
			long long lo = 0ll;
			long long mid;
			while(lo < hi){
				mid = (lo + hi)/2ll;
				if(query(x,y-mid)){
					lo = mid+1ll;
				}else{
					hi = mid;
				}
			}
			byd = y-lo;
			break;
		}
	}
	return byu - byd - 1ll;
}
int main(){
	scanf("%d",&n);
	long long x0,y0;
	scanf("%lld%lld",&x0,&y0);
	long long m = getsidelength(x0,y0);
	//printf("%lld\n",m);
	auto v0 = search(x0,y0,up);
	auto v1 = search(x0,y0,down);
	auto v2 = search(x0,y0,lleft);
	auto v3 = search(x0,y0,rright);
	int mask = 0;
	if(v0 != NOPE) mask++;
	mask *= 2;
	if(v1 != NOPE) mask++;
	mask *= 2;
	if(v2 != NOPE) mask++;
	mask *= 2;
	if(v3 != NOPE) mask++;
	pair<long long,long long> nxt;
	//printf("DBG %d\n",mask);
	switch(mask){
		case 5:
		nxt = search(v1.first,v1.second,down);
		if(nxt == NOPE){
			nxt.first = x0 + m;
			nxt.second = y0 - m;
		}else{
			nxt.first = v1.first + 2ll*m;
			nxt.second = v1.second;
		}
		break;

		case 6:
		nxt = search(v1.first,v1.second,down);
		if(nxt == NOPE){
			nxt.first = x0 - m;
			nxt.second = y0 - m;
		}else{
			nxt.first = v1.first - 2ll*m;
			nxt.second = v1.second;
		}
		break;

		case 7:
		nxt = v1;
		break;

		case 9:
		nxt = search(v0.first,v0.second,up);
		if(nxt == NOPE){
			nxt.first = x0 + m;
			nxt.second = y0 + m;
		}else{
			nxt.first = v0.first + 2ll*m;
			nxt.second = v0.second;
		}
		break;

		case 10:
		nxt = search(v0.first,v0.second,up);
		if(nxt == NOPE){
			nxt.first = x0 - m;
			nxt.second = y0 + m;
		}else{
			nxt.first = v0.first - 2ll*m;
			nxt.second = v0.second;
		}
		break;

		case 11:
		nxt = v0;
		break;

		case 13:
		nxt = v3;
		break;

		case 14:
		nxt = v2;
		break;

		case 15:
		nxt = make_pair(x0,y0);
		break;
	}
	long long x = nxt.first;
	long long y = nxt.second;
	//printf("DBGDBG %d %d\n",x,y);
	long long lo = 0;
	long long hi = m+1;
	long long mid;
	long long byu = 0;
	long long byd = 0;
	long long bxl = 0;
	long long bxr = 0;
	while(lo < hi){
		mid = (lo + hi)/2ll;
		if(query(x,y+mid)){
			lo = mid+1ll;
		}else{
			hi = mid;
		}
	}
	byu = y+lo;
	lo = 0ll;
	hi = m+1ll;
	while(lo < hi){
		mid = (lo + hi)/2ll;
		if(query(x,y-mid)){
			lo = mid+1ll;
		}else{
			hi = mid;
		}
	}
	byd = y-lo;
	lo = 0ll;
	hi = m+1ll;
	while(lo < hi){
		mid = (lo + hi)/2ll;
		if(query(x-mid,y)){
			lo = mid+1ll;
		}else{
			hi = mid;
		}
	}
	bxl = x-lo;
	lo = 0ll;
	hi = m+1ll;
	while(lo < hi){
		mid = (lo + hi)/2ll;
		if(query(x+mid,y)){
			lo = mid+1ll;
		}else{
			hi = mid;
		}
	}
	bxr = x+lo;
	printf("solution %lld %lld\n",(bxl + bxr)/2ll,(byd + byu)/2ll);
	return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'bool query(long long int, long long int)':
aliens.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",in);
  ~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
aliens.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&x0,&y0);
  ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10