# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1190175 | amm_oux | Aliens (IOI07_aliens) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std ;
using ll = long long ;
#define vll vector<ll>
#define vvll vector<vll>
ll pow[30] ;
void powsof2 (){
ll p = 1 ;
pow[0] = 0 ;
pow[1] = 1 ;
for (int i = 2 ; i < 30 ; i++){
p*=2 ;
pow[i] = p ;
}
}
void solve (){
ll N ,X , Y ;
int j = 1 ;
cin >> N >> X >> Y ;
bool response = 1;
string res ;
while (response && X+pow[j] < N +1 ){
cout << "examine " << X+pow[j] << " " << Y << endl ;
cin >> res ;
if (res == "true") {response = 1 ; j++ ; }
else {response = 0 ;}
}
if (X+pow[j] < N +1) {
cout << "examine " << N << " " << Y << endl ; cin >> res ;
if (res == "true") {Xd = N ; }
} Xpr = X+pow[j-1] ; Xf = min (N , X+pow[j] ) ;
while (Xd < 0 && Xf - Xpr > 1) {
ll mid = Xpr + (Xf - Xprev)/2 ;
cout << "examine " << mid << " " << Y << endl ;
cin >> res ;
if (res == "true") { Xpr = mid ; }
else {Xf = mid ;}
} Xd = Xpr ;
response = 1 ; j = 1 ;
while (response && X-pow[j] > 0 ){
cout << "examine " << X-pow[j] << " " << Y << endl ;
cin >> res ;
if (res == "true") {response = 1 ; j++ ; }
else {response = 0 ;}
}
if (X-pow[j] < 1) {
cout << "examine " << 1 << " " << Y << endl ; cin >> res ;
if (res == "true") {Xg = 1 ; }
} Xpr = X-pow[j-1] ; Xf = max (1 , X-pow[j] ) ;
while (Xg < 0 && Xpr - Xf > 1) {
ll mid = Xpr - (Xpr - Xf)/2 ;
cout << "examine " << mid << " " << Y << endl ;
cin >> res ;
if (res == "true") { Xpr = mid ; }
else {Xf = mid ;}
} Xg = Xpr ;
M = Xd - Xg ;
response = 1 ; j = 1 ;
while (response && Y+pow[j] < N+1 ){
cout << "examine " << X<< " " << Y+pow[j] << endl ;
cin >> res ;
if (res == "true") {response = 1 ; j++ ; }
else {response = 0 ;}
}
if (Y+pow[j] > N) {
cout << "examine " << X << " " << N << endl ; cin >> res ;
if (res == "true") {Yu = N ; }
} Ypr = Y+pow[j-1] ; Yf = min (Y+pow[j] , N ) ;
while (Yu < 0 && Yf - Ypr > 1) {
ll mid = Ypr + (Yf - Ypr)/2 ;
cout << "examine " << X << " " << mid << endl ;
cin >> res ;
if (res == "true") { Ypr = mid ; }
else {Yf = mid ;}
} Yu = Ypr ;
int sypos = 5 ;
int sxpos = 5 ;
for (int i = 0 ; i < 4 ; i++) {
if (Xd + (4-i)*M > N ) continue ;
else {
cout << "examine " << Xd + (4-i)*M << " " << Y << endl ; cin >> res ;
if (res == "true") { sxpos = i+1 ; break ;}
}
}
for (int i = 0 ; i < 4 ; i++) {
if (Yu + (4-i)*M > N ) continue ;
else {
cout << "examine " << X << " " << Yu + (4-i)*M << endl ; cin >> res ;
if (res == "true") { sypos = i+1 ; break ;}
}
}
cout << "solution " << Xd + (3-sxpos)*M - M/2 << " " << Yu + (3-sypos)*M - M/2 << endl;
}
int main (){
ll t = 1 ;
//ios :: sync_with_stdio(false) ; cin.tie(0);
while (t--)
solve();
}