제출 #103896

#제출 시각아이디문제언어결과실행 시간메모리
103896turbat커다란 상품 (IOI17_prize)C++14
20 / 100
41 ms888 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_pairdefine F first #define S second #define N 200005 int mx, fen[N], cnt; void add(int x){ x++, cnt++; while (x < N){ fen[x]++; x += x & -x; } } int query(int x){ x++; int s = 0; while (x > 0){ s += fen[x]; x -= x & -x; } return s; } int gg(int l, int r){ if (l == r) { vi tmp = ask(l); add(l); return tmp[0] + tmp[1] == 0 ? l : -1; } vi tmp, tmp1; while (l <= r){ tmp = ask(l); if (tmp[0] + tmp[1] == 0) return l; if (tmp[0] + tmp[1] == mx) break; add(l); l++; } while(l <= r){ tmp1 = ask(r); if (tmp1[0] + tmp1[1] == 0) return r; if (tmp1[0] + tmp1[1] == mx) break; add(r); r--; } if (l > r) return -1; if (tmp1[0] == tmp[0]) return -1; int mid = (l + r) / 2; return max(gg(l, mid), gg(mid + 1, r)); } int find_best(int n) { if (n <= 5000) for(int i = 0; i < n; i++) { std::vector<int> res = ask(i); if(res[0] + res[1] == 0) return i; } vector <vi> vc; for (int i = 0;i < 450;i++){ vi ans = ask(i); vc.pb(ans); int t = ans[0] + ans[1]; if (!t) return i; mx = max(mx, t); } for (int i = 0;i < 450;i++) if (mx != vc[i][0] + vc[i][1]) add(i); return gg(450, n - 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...