oj.uz

Submission #54315

# Submission time Handle Problem Language Result Execution time Memory
54315 2018-07-03T06:49:23 Z 김세빈(#1473) Aliens (IOI07_aliens) C++11
100 / 100
 4 ms 572 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, m;

bool check(ll x, ll y)
{
	char ret[11];
	
	if(x > n || x < 1 || y > n || y < 1) return 0;
	
	printf("examine %lld %lld\n", x, y);
	
	fflush(stdout);
	
	scanf("%s", ret);
	
	return ret[0] == 't';
}

int main()
{
	ll x, y, s, e, mid;
	ll x1, x2, y1, y2;
	
	scanf("%lld%lld%lld", &n, &x, &y);
	
	for(s=x,e=n;s<=e;){
		mid = s+e >> 1;
		if(check(mid, y) && check((x + mid*2) / 3, y) && check((x*2 + mid) / 3, y)) s = mid + 1;
		else e = mid - 1;
	}
	
	x2 = s - 1;
	
	for(s=1,e=x;s<=e;){
		mid = s+e >> 1;
		if(check(mid, y) && check((x + mid*2) / 3, y) && check((x*2 + mid) / 3, y)) e = mid - 1;
		else s = mid + 1;
	}
	
	x1 = e + 1;
	
	if(y <= n-y){
		for(s=1,e=y;s<=e;){
			mid = s+e >> 1;
			if(check(x, mid) && check(x, (y + mid*2) / 3) && check(x, (y*2 + mid) / 3)) e = mid - 1;
			else s = mid + 1;
		}
		
		y1 = e + 1;
		y2 = x2 - x1 + y1;
	}
	else{
		for(s=y,e=n;s<=e;){
			mid = s+e >> 1;
			if(check(x, mid) && check(x, (y + mid*2) / 3) && check(x, (y*2 + mid) / 3)) s = mid + 1;
			else e = mid - 1;
		}
		
		y2 = s - 1;
		y1 = y2 - x2 + x1;
	}
	
	m = x2 - x1 + 1;
	x = (x2 + x1) / 2, y = (y2 + y1) / 2;
	
	if(check(x - m*2, y)){
		if(check(x - m*3, y - m)){
			if(check(x - m*3, y - m*3)){
				if(check(x - m*4, y - m*4)) x -= m*2, y -= m*2;
				else x -= m, y -= m;
			}
			else{
				if(check(x - m*4, y - m*2)) x -= m*2;
				else x -= m, y += m;
			}
		}
		else{
			if(check(x - m*2, y - m*2)){
				if(check(x - m*2, y - m*4)) y -= m*2;
			}
			else{
				if(check(x - m*4, y)) x -= m*2, y += m*2;
				else y += m*2;
			}
		}
	}
	else{
		if(check(x, y - m*2)){
			if(check(x - m, y - m*3)) x += m, y -= m;
			else if(check(x, y - m*4)) x += m*2, y -= m*2;
			else x += m*2;
		}
		else{
			if(check(x - m, y - m)) x += m, y += m;
			else x += m*2, y += m*2;
		}
	}
	
	printf("solution %lld %lld\n", x, y);
	
	fflush(stdout);
	
	return 0;
}

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:32:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s+e >> 1;
         ~^~
aliens.cpp:40:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s+e >> 1;
         ~^~
aliens.cpp:49:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
aliens.cpp:59:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
aliens.cpp: In function 'bool check(ll, ll)':
aliens.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", ret);
  ~~~~~^~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:29: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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
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 Correct 4 ms 572 KB Output is correct

Subtask #10
10.0 / 10.0

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