Submission #1018512

#TimeUsernameProblemLanguageResultExecution timeMemory
1018512socpiteHotter Colder (IOI10_hottercolder)C++14
91.67 / 100
443 ms8248 KiB
#include "grader.h" #include <bits/stdc++.h> using namespace std; mt19937 rng(69420); int n; int solve(int l, int r, int prv){ // cout << l << " " << r << " " << prv << endl; if(l == r)return l; if(l == 1){ if(r <= 3){ int tmp = Guess(1); if(tmp == 1)return 1; if(tmp == 0)return 2; return r; } int dist = (r - l + 1)/4, g = max(1, dist - 3); int tmp = Guess(g); if(tmp == -1)return solve((g+r)/2 + 1, r, g); if(tmp == 0)return (g+r)/2; tmp = Guess(g+2); if(tmp == 0)return g+1; if(tmp == -1)return solve(1, g+2, g+2); return solve(g+2, (g+r-1)/2, g+2); } else if(r == n){ if(r - l + 1 <= 3){ int tmp = Guess(n); if(tmp == 1)return n; if(tmp == 0)return n-1; return l; } int dist = (r - l + 1)/4, g = min(n, r - dist + 4); int tmp = Guess(g); if(tmp == -1)return solve(l, (l+g-1)/2, g); if(tmp == 0)return (l+g)/2; tmp = Guess(g-2); if(tmp == 0)return g-1; if(tmp == -1)return solve(g-2, r, g-2); return solve((g+l)/2 + 1, g-2, g-2); } else { int mid = (l+r)>>1; if(prv == mid){ int tmp = Guess(prv + 2); if(tmp == -1)return solve(l, prv, prv+2); if(tmp == 0)return prv+1; if(tmp == 1)return solve(prv+2, r, prv+2); } int qq = max(1, 2*mid - prv); qq = min(qq, n); int tmp = Guess(qq); if(prv < mid)tmp*=-1; if(tmp == -1)return solve((qq + prv)/2 + 1, r, qq); if(tmp == 0)return (qq+prv)/2; return solve(l, (qq+prv-1)/2, qq); } } int HC(int N){ n = N; if(n <= 3){ Guess(n); return solve(1, n, 1); } else { int mid = n/2; Guess(mid-1); int tmp = Guess(mid+1); if(tmp == 0)return mid; if(tmp == 1)return solve(mid+1, n, mid+1); return solve(1, mid+1, mid+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...