Submission #1253862

#TimeUsernameProblemLanguageResultExecution timeMemory
1253862Cookie커다란 상품 (IOI17_prize)C++20
20 / 100
28 ms6160 KiB
//#include "prize.h" #include<bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #define sz(v) (int)v.size() #define fi first #define se second using namespace std; static const int max_q = 10000; static int n; static int query_count = 0; static vector<int> g; static vector<vector<int> > rank_count; //#include "prize.h" vector<int>ask(int); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rr(int l, int r){ return(uniform_int_distribution<int>(l, r)(rng)); } int N = 2e5 + 5; int MX = 0; vector<pair<int, int>>special; vector<int>memo[200005]; set<int>unvisited; int Q = 10000; int bit[200005 + 1]; void upd(int p, int v){ while(p <= N){ bit[p] += v; p += p & (-p); } } int gett(int p){ int ans = 0; while(p){ ans += bit[p]; p -= p & (-p); } return(ans); } int kth(int x){ int pos = 0, sm = 0; for(int i = 17; i >= 0; i--){ if(pos + (1 << i) <= N && bit[pos + (1 << i)] + sm < x){ pos += (1 << i); sm += bit[pos]; } } return(pos + 1); } pair<vector<int>, bool>get(int x){ if(sz(memo[x]) == 2)return(make_pair(memo[x], 0)); Q--; memo[x] = ask(x); if(memo[x][0] + memo[x][1] < MX){ special.push_back(make_pair(x, memo[x][0] + memo[x][1])); return(make_pair(memo[x], 1)); } return(make_pair(memo[x], 0)); } int find_best(int n) { N = n; int pos, L = 1, R = n, cntzero = 0, cntone = 0; for(int i = 0; i < n; i++){ upd(i + 1, 1); } for(int i = 0; i < 450; i++){ int cand = i; get(cand); MX = max(MX, memo[cand][0] + memo[cand][1]); memo[cand].clear(); } special.clear(); while(Q){ //assert(L <= R); int mid = (L + R) >> 1; //cerr << mid << "\n"; pos = kth(mid) - 1; assert(sz(memo[pos]) == 0); upd(pos + 1, -1); //assert(pos >= L && pos <= R); auto [cnt, isspecial] = get(pos); if(cnt[0] + cnt[1] == 0)return(pos); int rnk = cnt[0] + cnt[1]; for(auto i: special){ if(i.se < rnk){ if(i.fi < pos){ cnt[0]--; }else if(i.fi > pos){ cnt[1]--; } } } assert(cnt[0] >= 0 && cnt[1] >= 0); //assert(isspecial || (cnt[0] >= cntzero && cnt[1] >= cntone)); cnt[0] -= cntzero; cnt[1] -= cntone; if(cnt[0] > cnt[1]){ R = mid - 1; cntone += cnt[1]; }else{ L = mid; R--; cntzero += cnt[0]; } if(isspecial){ L = 1; R = gett(n); cntzero = cntone = 0; } //assert(cnt[0] || cnt[1]); } //assert(0); return(1); } /* vector<int> ask(int i) { query_count++; if(query_count > max_q) { cerr << "Query limit exceeded" << endl; exit(0); } if(i < 0 || i >= n) { cerr << "Bad index: " << i << endl; exit(0); } vector<int> res(2); res[0] = rank_count[g[i] - 1][i + 1]; res[1] = rank_count[g[i] - 1][n] - res[0]; return res; } int main() { cin >> n; g.resize(n); for(int i = 0; i < n; i++) { cin >> g[i]; if(g[i] < 1) { cerr << "Invalid rank " << g[i] << " at index " << i << endl; exit(0); } } int max_rank = *max_element(g.begin(), g.end()); rank_count.resize(max_rank + 1, vector<int>(n + 1, 0)); for(int r = 0; r <= max_rank; r++) { for(int i = 1; i <= n; i++) { rank_count[r][i] = rank_count[r][i - 1]; if(g[i - 1] == r) rank_count[r][i]++; } } for(int i = 0; i <= n; i++) for(int r = 1; r <= max_rank; r++) rank_count[r][i] += rank_count[r - 1][i]; int res = find_best(n); cout << res << endl << "Query count: " << query_count << endl; return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...