oj.uz

Submission #79292

# Submission time Handle Problem Language Result Execution time Memory
79292 2018-10-12T06:50:17 Z Plurm Aliens (IOI07_aliens) C++11
40 / 100
 5 ms 716 KB 
#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;
	int yy = y;
	int xx = x;
	if(d == up){
		for(long long i = 1; yy+i <= (long long)n; i *= 2ll){
			if(query(x,yy+i)){
				if(sstate == 1){
					return make_pair(x,yy+i);
				}
			}else{
				if(sstate == 0){
					yy += i;
					sstate = 1;
					i = 1;
				}
			}
		}
		return NOPE;
	}else if(d == down){
		for(long long i = 1; yy-i > 0ll; i *= 2ll){
			if(query(x,yy-i)){
				if(sstate == 1){
					return make_pair(x,yy-i);
				}
			}else{
				if(sstate == 0){
					yy -= i;
					sstate = 1;
					i = 1;
				}
			}
		}
		return NOPE;
	}else if(d == lleft){
		for(long long i = 1; xx-i > 0ll; i *= 2ll){
			if(query(xx-i,y)){
				if(sstate == 1){
					return make_pair(xx-i,y);
				}
			}else{
				if(sstate == 0){
					xx -= i;
					sstate = 1;
					i = 1;
				}
			}
		}
		return NOPE;
	}else{
		for(long long i = 1; xx+i <= (long long)n; i *= 2ll){
			if(query(xx+i,y)){
				if(sstate == 1){
					return make_pair(xx+i,y);
				}
			}else{
				if(sstate == 0){
					xx += i;
					sstate = 1;
					i = 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

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:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
aliens.cpp:127: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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Incorrect 2 ms 456 KB Incorrect

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 456 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 496 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 572 KB Output is correct
2 Incorrect 4 ms 572 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 572 KB too many queries
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 572 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Incorrect 4 ms 716 KB too many queries