Submission #54358

#	Time	Username	Problem	Language	Result	Execution time	Memory
54358		khsoo01	Aliens (IOI07_aliens)	C++11	100 / 100	5 ms	552 KiB

aliens

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll n, x, y;

char a[15];

bool valid (ll A, ll B) {
	return (1 <= A && A <= n && 1 <= B && B <= n);
}

bool query (ll A, ll B) {
	if(!valid(A, B)) return false;
	printf("examine %lld %lld\n",A,B);
	fflush(stdout);
	scanf("%s",a);
	return (a[0] == 't');
}

pll get_bound (ll x, ll y, ll dx, ll dy) {
	ll B = 1;
	for(;;) {
		if(!valid(x+dx*B, y+dy*B)) {
			if(dx == 1) B = n-x;
			if(dx == -1) B = x-1;
			if(dy == 1) B = n-y;
			if(dy == -1) B = y-1;
			break;
		}
		if(!query(x+dx*B, y+dy*B)) break;
		B *= 2;
	}
	ll S = 0, E = B;
	while(S<E) {
		ll M = (S+E)/2+1;
		query(x+dx*M,y+dy*M) ? S = M : E = M-1;
	}
	return {x+dx*S, y+dy*S};
}

int main()
{
	scanf("%lld%lld%lld",&n,&x,&y);
	ll XS = get_bound(x, y, -1, 0).X, XE = get_bound(x, y, 1, 0).X, L = (XE - XS + 1);
	ll YS = get_bound(x, y, 0, -1).Y, YE = YS + L - 1;
	x = (XS+XE)/2;
	y = (YS+YE)/2;
	ll A = query(x-4*L, y), B = query(x-2*L, y), C = query(x+2*L, y), D = query(x+4*L, y);
	if(A + B + C + D == 1) {
		ll T = query(x, y-2*L);
		if(T) y -= L;
		else y += L;
		if(B) x -= L;
		else x += L;
	}
	else {
		ll P = query(x, y-2*L), Q = query(x, y-4*L);
		if(P + Q == 2) y -= 2*L;
		else if(P + Q == 0) y += 2*L;
		if(A + B == 2) x -= 2*L;
		else if(A + B == 0) x += 2*L;
	}
	printf("solution %lld %lld\n",x,y);
}

Compilation message (stderr)

aliens.cpp: In function 'bool query(ll, ll)':
aliens.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a);
  ~~~~~^~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&x,&y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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