Submission #104745

#TimeUsernameProblemLanguageResultExecution timeMemory
104745turbatThe Big Prize (IOI17_prize)C++14
90 / 100
66 ms2128 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; using vi = vector <int>; using pii = pair <int, int>; #define pb push_back #define mp make_pair #define F first #define S second #define N 200005 map < int, vector<int> > query; int mx; int fen[N]; bool u[N]; void add(int x){ x++; if (!u[x]) u[x] = 1; else return; while (x < N){ fen[x]++; x += (x & (-x)); } } int sum(int x){ x++; int s = 0; while (x){ s = s + fen[x]; x -= (x & (-x)); } return s; } vector < int > askk(int x){ if( query.find( x ) == query.end() ){ return query[x] = ask(x); } return query[x]; } int gg(int l, int r){ vi tmp; if (l > r) return -1; // cerr << l<<" " << r<< '\n'; if (l == r) { tmp = askk(l); add(l); if (tmp[0] + tmp[1] == 0) return l; return -1; } while(l <= r){ tmp = askk(r); if ((tmp[0] + tmp[1]) == 0) { add(r); return r; } if (tmp[0] + tmp[1] == mx) break; add(r); r--; } // cerr <<tmp[1]<<" "<< tmp[0] <<" "<< sum(l - 1)<< " "<< l << " "<< r<< endl; if (l > r) return -1; if (tmp[0] == sum(l - 1)) return -1; if (l == r) return gg(l, r); int mid = (l + r) / 2; int ind = gg(l , mid); if (ind != -1) return ind; if (tmp[0] != sum(mid)) return gg(mid + 1, r - 1); return - 1; } int find_best(int n) { int s[505]; for (int i = 0;i < 500;i++){ vi ans = askk(i); s[i] = ans[0] + ans[1]; if (!s[i]) return i; mx = max(mx, s[i]); } for (int i = 0;i < 500;i++) if (s[i] != mx) add(i); // cerr << sum(499)<< " "<< mx<< endl; return gg(500, n - 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...