Submission #197329

#TimeUsernameProblemLanguageResultExecution timeMemory
197329arnold518Aliens (IOI07_aliens)C++14
40 / 100
3063 ms508 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; struct Point { ll x, y; }; ll N, M, MM; Point S; bool query(Point p) { if(!(1<=p.x && p.x<=N && 1<=p.y && p.y<=N)) return false; printf("examine %d %d\n", p.x, p.y); fflush(stdout); char t[10]; scanf("%s", t); return t[0]=='t'; } void answer(Point p) { printf("solution %d %d\n", p.x, p.y); fflush(stdout); exit(0); } int main() { ll i, j; scanf("%lld%lld%lld", &N, &S.x, &S.y); ll l, r; ll lo=S.x, hi=N+1; while(lo+1<hi) { ll mid=lo+hi>>1; if(query({mid, S.y})) lo=mid; else hi=mid; } r=lo; lo=0, hi=S.x; while(lo+1<hi) { ll mid=lo+hi>>1; if(query({mid, S.y})) hi=mid; else lo=mid; } l=hi; if(!query({l+r>>1, S.y})) MM=(r-l+1)/3; else { if((r-l+1)%5==0 && !query({l+(r-l+1)/5, S.y})) MM=(r-l+1)/5; else MM=r-l+1; } for(i=S.x; i<N; i++) if(!query({i+1, S.y})) break; r=i; for(i=S.x; i>1; i--) if(!query({i-1, S.y})) break; l=i; M=r-l+1; S.x=(l+r)/2; for(i=S.y; i<N; i++) if(!query({S.x, i+1})) break; r=i; for(i=S.y; i>1; i--) if(!query({S.x, i-1})) break; l=i; S.y=(l+r)/2; assert(M==MM); int p1, p2, p3, p4; p1=query({S.x, S.y+M+M}); p2=query({S.x+M+M, S.y}); p3=query({S.x, S.y-M-M}); p4=query({S.x-M-M, S.y}); if(p1 && p2 && p3 && p4) answer({S.x, S.y}); if(p1 && p2 && p3 && !p4) answer({S.x+M+M, S.y}); if(!p1 && p2 && p3 && p4) answer({S.x, S.y-M-M}); if(p1 && !p2 && p3 && p4) answer({S.x-M-M, S.y}); if(p1 && p2 && !p3 && p4) answer({S.x, S.y+M+M}); if(p1 && p2) { if(query({S.x-M, S.y-M})) answer({S.x+M, S.y+M}); else answer({S.x+M+M, S.y+M+M}); } if(p2 && p3) { if(query({S.x-M, S.y+M})) answer({S.x+M, S.y-M}); else answer({S.x+M+M, S.y-M-M}); } if(p3 && p4) { if(query({S.x+M, S.y+M})) answer({S.x-M, S.y-M}); else answer({S.x-M-M, S.y-M-M}); } if(p4 && p1) { if(query({S.x+M, S.y-M})) answer({S.x-M, S.y+M}); else answer({S.x-M-M, S.y+M+M}); } }

Compilation message (stderr)

aliens.cpp: In function 'bool query(Point)':
aliens.cpp:16:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  printf("examine %d %d\n", p.x, p.y);
                            ~~~     ^
aliens.cpp:16:36: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll {aka long long int}' [-Wformat=]
aliens.cpp: In function 'void answer(Point)':
aliens.cpp:26:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  printf("solution %d %d\n", p.x, p.y);
                             ~~~     ^
aliens.cpp:26:37: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll {aka long long int}' [-Wformat=]
aliens.cpp: In function 'int main()':
aliens.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=lo+hi>>1;
          ~~^~~
aliens.cpp:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=lo+hi>>1;
          ~~^~~
aliens.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(!query({l+r>>1, S.y})) MM=(r-l+1)/3;
             ~^~
aliens.cpp:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=S.x; i<N; i++) if(!query({i+1, S.y})) break; r=i;
  ^~~
aliens.cpp:64:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=S.x; i<N; i++) if(!query({i+1, S.y})) break; r=i;
                                                     ^
aliens.cpp:65:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=S.x; i>1; i--) if(!query({i-1, S.y})) break; l=i;
  ^~~
aliens.cpp:65:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=S.x; i>1; i--) if(!query({i-1, S.y})) break; l=i;
                                                     ^
aliens.cpp:68:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=S.y; i<N; i++) if(!query({S.x, i+1})) break; r=i;
  ^~~
aliens.cpp:68:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=S.y; i<N; i++) if(!query({S.x, i+1})) break; r=i;
                                                     ^
aliens.cpp:69:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=S.y; i>1; i--) if(!query({S.x, i-1})) break; l=i;
  ^~~
aliens.cpp:69:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=S.y; i>1; i--) if(!query({S.x, i-1})) break; l=i;
                                                     ^
aliens.cpp:33:8: warning: unused variable 'j' [-Wunused-variable]
  ll i, j;
        ^
aliens.cpp: In function 'bool query(Point)':
aliens.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", t);
  ~~~~~^~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &S.x, &S.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...