oj.uz

Submission #54309

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

using namespace std;

typedef long long ll;

ll n, m, cnt;
ll ans_x, ans_y, ans_sz;

bool yeah(ll x, ll y)
{
	if(x < ans_x - ans_sz/2 - ans_sz*2 || x > ans_x + ans_sz/2 + ans_sz*2) return 0;
	if(y < ans_y - ans_sz/2 - ans_sz*2 || y > ans_y + ans_sz/2 + ans_sz*2) return 0;
	
	x = (x - ans_x + ans_sz/2 + ans_sz*2) / ans_sz;
	y = (y - ans_y + ans_sz/2 + ans_sz*2) / ans_sz;
	
	return (x + y + 1) % 2;
} 

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

int f(ll x, ll y)
{
	ll 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;
	
//	printf("%lld %lld %lld %lld %lld\n", x1, x2, y1, y2, m);
	
	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, y - m*4)) 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;
}

int main()
{
	ll x, y;
	
	scanf("%lld", &n);
//	scanf("%lld%lld%lld", &ans_x, &ans_y, &ans_sz);
	scanf("%lld%lld", &x, &y);
	
	f(x, y);
	
	return 0;
}

Compilation message

aliens.cpp: In function 'bool check(ll, ll)':
aliens.cpp:28:24: warning: division by zero [-Wdiv-by-zero]
  if(cnt > 300) return 1/0;
                       ~^~
aliens.cpp: In function 'int f(ll, ll)':
aliens.cpp:49:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s+e >> 1;
         ~^~
aliens.cpp:57:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s+e >> 1;
         ~^~
aliens.cpp:66:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
aliens.cpp:76:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
aliens.cpp: In function 'bool check(ll, ll)':
aliens.cpp:34: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:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
aliens.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &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 516 KB Output is correct
2 Correct 2 ms 516 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 572 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 3 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 4 ms 572 KB Output is correct
3 Correct 4 ms 572 KB Output is correct