제출 #436795

#제출 시각아이디문제언어결과실행 시간메모리
436795biggAliens (IOI07_aliens)C++14
100 / 100
3 ms296 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; #define debug(args...) //fprintf(stderr, args) ll xo, yo; int cnt; bool examine(ll x, ll y){ //debug("EXAMINING %lld %lld", x, y); if(x <= 0 || x > n || y <= 0 || y > n) return false; cnt++; 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){ fprintf(stderr, "%d\n", cnt); 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); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...