Submission #79224

#TimeUsernameProblemLanguageResultExecution timeMemory
79224PlurmAliens (IOI07_aliens)C++11
0 / 100
3 ms656 KiB
#include <bits/stdc++.h> using namespace std; enum dir{ up, down, lleft, rright }; int n; const pair<int,int> NOPE = make_pair(-1,-1); map<pair<long long,long long>,bool> mp; bool query(long long x,long long y){ if(x <= 0 || y <= 0 || x > n || y > n) return false; if(mp.find(make_pair(x,y)) != mp.end()) return mp[make_pair(x,y)]; printf("examine %lld %lld\n",x,y); fflush(stdout); char in[8]; scanf("%s",in); mp[make_pair(x,y)] = in[0] == 't'; return in[0] == 't'; } pair<int,int> search(long long x,long long y,dir d){ int sstate = 0; if(d == up){ for(long long i = 1; y+i <= (long long)n; i *= 2ll){ if(query(x,y+i)){ if(sstate == 1){ return make_pair(x,y+i); } }else{ if(sstate == 0) sstate = 1; } } return NOPE; }else if(d == down){ for(long long i = 1; y-i > 0ll; i *= 2ll){ if(query(x,y-i)){ if(sstate == 1){ return make_pair(x,y-i); } }else{ if(sstate == 0) sstate = 1; } } return NOPE; }else if(d == lleft){ for(long long i = 1; x-i > 0ll; i *= 2ll){ if(query(x-i,y)){ if(sstate == 1){ return make_pair(x-i,y); } }else{ if(sstate == 0) sstate = 1; } } return NOPE; }else{ for(long long i = 1; x+i <= (long long)n; i *= 2ll){ if(query(x+i,y)){ if(sstate == 1){ return make_pair(x+i,y); } }else{ if(sstate == 0) sstate = 1; } } return NOPE; } } int getsidelength(long long x,long long y){ int byu = -1; int byd = -1; for(long long i = 1; ; i *= 2ll){ if(!query(x,y+i)){ int hi = min(i,n-y); int lo = 0; int mid; while(lo < hi){ mid = (lo + hi)/2; if(query(x,y+mid)){ lo = mid+1; }else{ hi = mid; } } byu = y+lo; break; } } for(long long i = 1; ; i *= 2ll){ if(!query(x,y-i)){ int hi = min(i,y); int lo = 0; int mid; while(lo < hi){ mid = (lo + hi)/2; if(query(x,y-mid)){ lo = mid+1; }else{ hi = mid; } } byd = y-lo; break; } } return byu - byd - 1; } int main(){ scanf("%d",&n); int x0,y0; scanf("%d%d",&x0,&y0); int m = getsidelength(x0,y0); //printf("%d\n",m); auto v0 = search(x0,y0,up); auto v1 = search(x0,y0,down); auto v2 = search(x0,y0,lleft); auto v3 = search(x0,y0,rright); int mask = 0; if(v0 != NOPE) mask++; mask *= 2; if(v1 != NOPE) mask++; mask *= 2; if(v2 != NOPE) mask++; mask *= 2; if(v3 != NOPE) mask++; pair<int,int> nxt; //printf("DBG %d\n",mask); switch(mask){ case 5: nxt = search(v1.first,v1.second,down); if(nxt == NOPE){ nxt.first = x0 + m; nxt.second = y0 - m; }else{ nxt.first = v1.first + 2*m; nxt.second = v1.second; } break; case 6: nxt = search(v1.first,v1.second,down); if(nxt == NOPE){ nxt.first = x0 - m; nxt.second = y0 - m; }else{ nxt.first = v1.first - 2*m; nxt.second = v1.second; } break; case 7: nxt = v1; break; case 9: nxt = search(v0.first,v0.second,up); if(nxt == NOPE){ nxt.first = x0 + m; nxt.second = y0 + m; }else{ nxt.first = v0.first + 2*m; nxt.second = v0.second; } break; case 10: nxt = search(v0.first,v0.second,up); if(nxt == NOPE){ nxt.first = x0 - m; nxt.second = y0 + m; }else{ nxt.first = v0.first - 2*m; nxt.second = v0.second; } break; case 11: nxt = v0; break; case 13: nxt = v3; break; case 14: nxt = v2; break; case 15: nxt = make_pair(x0,y0); break; } int x = nxt.first; int y = nxt.second; //printf("DBGDBG %d %d\n",x,y); int lo = 0; int hi = m+1; int mid; int byu = 0; int byd = 0; int bxl = 0; int bxr = 0; while(lo < hi){ mid = (lo + hi)/2; if(query(x,y+mid)){ lo = mid+1; }else{ hi = mid; } } byu = y+lo; lo = 0; hi = m+1; while(lo < hi){ mid = (lo + hi)/2; if(query(x,y-mid)){ lo = mid+1; }else{ hi = mid; } } byd = y-lo; lo = 0; hi = m+1; while(lo < hi){ mid = (lo + hi)/2; if(query(x-mid,y)){ lo = mid+1; }else{ hi = mid; } } bxl = x-lo; lo = 0; hi = m+1; while(lo < hi){ mid = (lo + hi)/2; if(query(x+mid,y)){ lo = mid+1; }else{ hi = mid; } } bxr = x+lo; printf("solution %d %d\n",(bxl + bxr)/2,(byd + byu)/2); return 0; }

Compilation message (stderr)

aliens.cpp: In function 'bool query(long long int, long long int)':
aliens.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",in);
  ~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
aliens.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&x0,&y0);
  ~~~~~^~~~~~~~~~~~~~~~
#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...