oj.uz

Submission #122278

# Submission time Handle Problem Language Result Execution time Memory
122278 2019-06-28T03:50:47 Z khulegub Aliens (IOI07_aliens) C++14
100 / 100
 3 ms 384 KB 
#include<bits/stdc++.h>
#define unen true
#define hud false
using namespace std;
typedef long long i64;
 
i64 n;
 
// i64 read_int(){
// 	char r;
// 	bool start=false,neg=false;
// 	i64 ret=0;
// 	while(true){
// 		r = getchar();
// 		if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
// 			continue;
// 		}
// 		if((r-'0'<0 || r-'0'>9) && r!='-' && start){
// 			break;
// 		}
// 		if(start) ret *= 10;
// 		start = true;
// 		if(r=='-') neg = true;
// 		else ret+=r-'0';
// 	}
// 	if(!neg)
// 		return ret;
// 	else
// 		return -ret;
// }
i64 read_int(){
	bool minus = false;
	i64 result = 0;
	char ch;
	ch = getchar();
	while (true){
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true){
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
bool exam(i64 x, i64 y){
	if(x < 1 || y < 1 || x > n || y > n) return 0;
	cout << "examine " << x << ' ' << y << endl;
	string ans;
	cin >> ans;
	return (ans[0] == 't');
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	i64 X, Y, x0, y0; // X, Y - chigluulegch
	i64 zuun, baruun, deesh, doosh;
	i64 usreh, l, r, m;
	n = read_int();
	x0 = read_int();
	y0 = read_int();
	// cin >> n >> x0 >> y0;
 
	X = -1, Y = 0;
	usreh = 1;
	while( exam(x0 + X * usreh, y0 + Y * usreh) ){
		usreh = usreh << 1;
	}
	l = usreh / 2, r = usreh;
	while( l + 1 < r ){
		i64 mid = (l + r) >> 1;
		if( exam(x0 + X * mid, y0 + Y * mid) ) l = mid;
		else r = mid;
	}
	zuun = l;
	//
	X = 1, Y = 0;
	usreh = 1;
	while( exam(x0 + X * usreh, y0 + Y * usreh) ){
		usreh = usreh << 1;
	}
	l = usreh / 2, r = usreh;
	while( l + 1< r ){
		i64 mid = (l + r) >> 1;
		if( exam(x0 + X * mid, y0 + Y * mid) ) l = mid;
		else r = mid;
	}
	baruun = l;
	//
	X = 0, Y = -1;
	usreh = 1;
	while( exam(x0 + X * usreh, y0 + Y * usreh) ){
		usreh = usreh << 1;
	}
	l = usreh / 2, r = usreh;
	while( l + 1 < r ){
		i64 mid = (l + r) >> 1;
		if( exam(x0 + X * mid, y0 + Y * mid) ) l = mid;
		else r = mid;
	}
	doosh = l;
	//
	X = 0, Y = 1;
	usreh = 1;
	while( exam(x0 + X * usreh, y0 + Y * usreh) ){
		usreh = usreh << 1;
	}
	l = usreh / 2, r = usreh;
	while( l + 1 < r ){
		i64 mid = (l + r) >> 1;
		if( exam(x0 + X * mid, y0 + Y * mid) ) l = mid;
		else r = mid;
	}
	deesh = l;
	//
	m = deesh + doosh + 1;
	x0 = x0 - zuun + (m / 2); //centering
	y0 = y0 - doosh + (m / 2);
	//wtf ene yu yum be sd
	while( exam(x0 - m, y0 - m) ) x0 -= m, y0 -= m;
	while( exam(x0 - 2 * m, y0) ) x0 -= 2 * m;
	while( exam(x0, y0 - 2 * m) ) y0 -= 2 * m;
 
    cout << "solution " << x0 + 2 * m << ' ' << y0 + 2 * m << endl;
	return 0;
}

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:62:12: warning: variable 'baruun' set but not used [-Wunused-but-set-variable]
  i64 zuun, baruun, deesh, doosh;
            ^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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