oj.uz

Submission #54358

# Submission time Handle Problem Language Result Execution time Memory
54358 2018-07-03T08:17:15 Z khsoo01 Aliens (IOI07_aliens) C++11
100 / 100
 5 ms 552 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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