Submission #989701

#TimeUsernameProblemLanguageResultExecution timeMemory
989701dnassAliens (IOI07_aliens)C++17
80 / 100
2 ms344 KiB
#include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<cmath> #include<random> #include<bitset> #include<string> #include<queue> #include<stack> #include<set> #include<map> #include<deque> #include<chrono> using namespace std; typedef long long int lld; typedef long double lf; #define INF 1000000000000000000LL #define MOD 1000000007LL #define ff first #define ss second int n, x, y, l, r, mid, xl, xr, xmid, diff; int ask(int xt, int yt){ if(xt<=0||yt<=0||xt>n||yt>n) return 0; cout << "examine " << xt << " " << yt << endl; string rt; cin >> rt; return rt[0]=='t'; } int main(){ cin >> n >> x >> y; l = x, r = n+1; while(l+1<r){ int mid = (l+r)/2; if(ask(mid, y)) l = mid; else r = mid; } x = l; //cout << "Found right edge: " << x << " " << y << endl; l = y, r = n+1; while(l+1<r){ int mid = (l+r)/2; if(ask(x, mid)) l = mid; else r = mid; } y = l; //cout << "Found top right of square: " << x << " " << y << endl; xl = x, xr = n+1, diff = y-x; while(xl+1<xr){ xmid = (xl+xr)/2; if(ask(xmid, xmid+diff)) xl = xmid; else xr = xmid; } x = xl, y = xl+diff; //cout << "Found top right of diagonal: " << x << " " << y << endl; xl = 0, xr = x, diff = y-x; while(xl+1<xr){ xmid = (xl+xr)/2; if(ask(xmid, xmid+diff)) xr = xmid; else xl = xmid; } x = (x+xr)/2, y = (y+xr+diff)/2; //cout << "Found center of diagonal: " << x << " " << y << endl; xl = 0, xr = x, diff = y+x; while(xl+1<xr){ xmid = (xl+xr)/2; if(ask(xmid, diff-xmid)) xr = xmid; else xl = xmid; } x = xr, y = diff-xr; //cout << "Found top left of main diagonal: " << x << " " << y << endl; xl = x, xr = n+1, diff = y+x; while(xl+1<xr){ xmid = (xl+xr)/2; if(ask(xmid, diff-xmid)) xl = xmid; else xr = xmid; } x = (x+xl)/2, y = (y+diff-xl)/2; cout << "solution " << x << " " << y << endl; return 0; }
#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...