제출 #432174

#제출 시각아이디문제언어결과실행 시간메모리
432174jeroenodb커다란 상품 (IOI17_prize)C++14
20 / 100
106 ms11012 KiB
#ifndef GRADER #include "prize.h" #endif #include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1e9; map<int,vi> qs; vi test(int i) { if(qs.count(i)) return qs[i]; else return qs[i] = ask(i); } template<typename T> struct fenwick { int n; vector<T> fen; fenwick(){} fenwick(int nn) { fen.resize(nn+1); n = nn; } auto sum(int i) { T ans = 0; while(i) { ans+=fen[i]; i&=i-1; } return ans; } auto query(int l, int r) { return sum(r+1)-sum(l); } void update(int i, T val) { ++i; while(i<=n) { fen[i]+=val; i+= i&(-i); } } }; int worst(int i) { if(i==0) return 0; return sqrt(i-1); } int find_best(int n) { int mx=worst(n)+worst(worst(n))+worst(worst(worst(n)))+worst(worst(worst(worst(n)))); int step = max(1,n/mx); int lolly=0; for(int i=0;i<n;i+=step) { auto v = test(i); lolly = max(lolly,v[0]+v[1]); } int left=lolly; set<int> cand; fenwick<int> fen(n); for(int i=0;i<n;++i) cand.insert(i); while(left--) { int lo=0,hi=n-1; while(lo<=hi) { int mid = (lo+hi)/2; auto it = cand.lower_bound(mid); if(it==cand.end()) hi=mid-1; auto check = *it; if(check>hi) break; auto v = test(check); if(v[0]+v[1]==lolly) { if(v[0]>fen.query(0,check)) { hi = mid-1; } else lo = mid+1; } else { if(v[0]+v[1]==0) return check; cand.erase(check); fen.update(check,1); break; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...