oj.uz

Submission #436794

# Submission time Handle Problem Language Result Execution time Memory
436794 2021-06-24T23:53:15 Z bigg Aliens (IOI07_aliens) C++14
100 / 100
 3 ms 200 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n;
#define debug(args...) //fprintf(stderr, args)
ll xo, yo;

bool examine(ll x, ll y){
	//debug("EXAMINING %lld %lld", x, y);
	if(x <= 0 || x > n || y <= 0 || y > n) return false;
	
	string s;
	cout << "examine " << x << " " << y << endl;
	cout.flush();
	cin >> s;
	if(s[0] == 't') return 1;
	return 0;
}

void solution(ll x, ll y){
	cout << "solution " << x << " " << y << endl; 
	cout.flush();
}

int main(){

	cin >> n >> xo >> yo;
	ll l, r;
	ll k = 1;
	while(examine(xo + k, yo)){
		k*=2;
	}
	if(k != 1){
		ll lo = xo, hi = xo + k;
		while(lo < hi){
			ll mid = (hi + lo)/2;
			if(hi == lo + 1) mid++;
			if(examine(mid,yo)) lo = mid;
			else hi = mid - 1;
		}
		r = lo;
	}else{
		r = xo;
	}
	k = 1;
	while(examine(xo - k, yo)){
		k*=2;
	}
	if(k != 1){
		ll lo = xo - k, hi = xo;
		while(lo < hi){
			ll mid = (hi + lo)/2;
			if(examine(mid,yo)) hi = mid;
			else lo = mid + 1;
		}
		l = hi;
	}else{
		l = xo;
	} 
	ll m = r - l + 1;
	ll u, d;
	ll hi = yo + m, lo = yo;
	while(lo < hi){
		ll mid = (hi + lo)/2;
		if(hi == lo + 1) mid++;
		if(examine(xo,mid)) lo = mid;
		else hi = mid-1;
	}
	u = lo;
	ll xc1 = (l) + m/2;
	ll yc1 = u - m/2;
	
	d = u - m + 1;
	debug("xc1 %lld yc1 %lld m %lld l %lld r %lld u %lld d %lld\n", xc1, yc1, m, l, r, u, d);
	int qtdcima = 0, qtdbaixo = 0;
	if(examine(xo,u + m + 1)){
		qtdcima++;
		if(examine(xo,u+3*m+1)) qtdcima++;
	}
	if(examine(xo,d-m-1)){
		qtdbaixo++;
		if(examine(xo,d-3*m-1)) qtdbaixo++;
	}
	int qtddir = 0, qtdesq = 0;
	if(examine(r+m+1,yo)){
		qtddir++;
		if(examine(r+3*m+1,yo)) qtddir++;
	}
	if(examine(l-m-1,yo)){
		qtdesq++;
		if(examine(l-3*m-1,yo)) qtdesq++;
	}
	if(qtddir == 2 && qtdbaixo == 2){
		ll ansx = xc1 + m/2 + m + m/2 + 1;
		ll ansy = yc1 - m/2 - m - m/2 - 1;
		solution(ansx,ansy);
 	}
 	if(qtddir == 1 && qtdesq == 1 && qtdbaixo == 2){
 		ll ansx = xc1;
 		ll ansy = yc1 - m/2 - m - m/2 - 1;
 		solution(ansx, ansy);
 	}
 	if(qtdesq == 2 && qtdbaixo == 2){
 		ll ansx = xc1 - m/2 - m - m/2 - 1;
 		ll ansy = yc1 - m/2 - m - m/2 - 1;
 		solution(ansx, ansy);
 	}
 	if(qtddir == 1 && qtdesq == 0 && qtdbaixo == 1 && qtdcima == 0){
 		ll ansx = xc1 + m/2 + 1 + m/2;
 		ll ansy = yc1 - m/2 - 1 - m/2;
 		solution(ansx, ansy);
 	}
 	if(qtddir == 0 && qtdesq == 1 && qtdbaixo == 1 && qtdcima == 0){
 		ll ansx = xc1 - m/2 - 1 - m/2;
 		ll ansy = yc1 - m/2 - 1 - m/2;
 		solution(ansx, ansy);
 	}
 	if(qtdbaixo == 1 && qtdcima == 1 && qtddir == 2){
 		ll ansx = xc1 + m/2 + m + m/2 + 1;
 		ll ansy = yc1;
 		solution(ansx, ansy);
 	}
 	if(qtdbaixo == 1 && qtdcima == 1 && qtddir == 1 && qtdesq == 1){
 		ll ansx = xc1;
 		ll ansy = yc1;
 		solution(ansx, ansy);
 	}
 	if(qtdbaixo == 1 && qtdcima == 1 && qtdesq == 2){
 		ll ansx = xc1 - m/2 - m - m/2 - 1;
 		ll ansy = yc1;
 		solution(ansx, ansy);
 	}
	if(qtdesq == 0 && qtddir == 1 && qtdcima == 1 && qtdbaixo == 0){
		ll ansx = xc1 + m/2 + 1 + m/2;
		ll ansy = yc1 + m/2 + 1 + m/2;
		solution(ansx, ansy);
	}
	if(qtdesq == 1 && qtddir == 0 && qtdcima == 1 && qtdbaixo == 0){
		ll ansx = xc1 - m/2 - 1 - m/2;
		ll ansy = yc1 + m/2 + 1 + m/2;
		solution(ansx, ansy);
	}
	if(qtdcima == 2 && qtddir == 2){
		ll ansx = xc1 + m/2 + m + m/2 + 1;
		ll ansy = yc1 + m/2 + m + m/2 + 1;
		solution(ansx, ansy);
	}
	if(qtdcima == 2 && qtddir == 1 && qtdesq == 1){
		ll ansx = xc1;
		ll ansy = yc1 + m/2 + m + m/2 + 1;
		solution(ansx, ansy);
	}
	if(qtdcima == 2 && qtdesq == 2){
		ll ansx = xc1 - m/2 - m - m/2 - 1;
		ll ansy = yc1 + m/2 + m + m/2 + 1;
		solution(ansx, ansy);
	}


}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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