Submission #73577

#TimeUsernameProblemLanguageResultExecution timeMemory
73577top34051Hotter Colder (IOI10_hottercolder)C++17
75 / 100
763 ms8168 KiB
#include "grader.h" #include<bits/stdc++.h> using namespace std; #define ll long long ll n,rev; ll kuy(ll x) { if(!rev) return x; return n-x+1; } ll small(ll l, ll r, ll a) { Guess(kuy(l)); ll res=Guess(kuy(r)); // printf("res = %d\n",res); if (res==0) return (l+r)/2; if (res==1) return r; return l; } ll solve(ll l, ll r, ll a) { // printf("solve [%d, %d] : %d [%d, %d]\n",kuy(l),kuy(r),a,l,r); if(l==r) return l; if(r-l+1<=3) return small(l,r,a); if(a==l) { ll b = (l*2+r)/3; ll c = (l+2*r)/3; ll tmp1 = Guess(kuy(b)), tmp2 = Guess(kuy(c)); // printf("b = %d c = %d tmp = %d and %d (%d, %d)\n",kuy(b),kuy(c),tmp1,tmp2,b,c); if(a!=b && tmp1==0) return (a+b)/2; if(b!=c && tmp2==0) return (b+c)/2; if(tmp2==-1) { if(tmp1==-1) return solve(l,(a+b)/2,c); else return solve((a+b)/2+1,(b+c)/2,c); } else return solve((b+c)/2+1,r,c); } else if(l<=a && a<=r) { ll b = (l+2*r)/3; ll tmp = Guess(kuy(b)); // printf("b = %d (%d)\n",kuy(b),b); if(a!=b && tmp==0) return (a+b)/2; if(tmp==-1) return solve(l,(a+b)/2,b); else return solve((a+b)/2+1,r,b); } else { ll b = l+r-a; // printf("b = %d (%d)\n",kuy(b)); ll tmp = Guess(kuy(b)); if(a!=b && tmp==0) return (a+b)/2; if(b < a) { if(tmp==1) return solve(l,(l+r)/2,b); return solve((l+r)/2+1,r,b); } else { if(tmp==1) return solve((l+r)/2+1,r,b); return solve(l,(l+r)/2,b); } } } int HC(int N) { n = N; Guess(N); ll tmp = Guess(1); if(tmp==0) return (1+N)/2; rev = 0; if(tmp==1) rev = 1; // printf("rev = %d\n",rev); if(rev) Guess(N); return kuy(solve(1,N,1)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...