제출 #731869

#제출 시각아이디문제언어결과실행 시간메모리
731869sentheta커다란 상품 (IOI17_prize)C++17
100 / 100
54 ms5256 KiB
#include "prize.h" // author : sentheta aka vanwij #include<iostream> #include<iomanip> #include<algorithm> #include<cassert> #include<random> #include<chrono> #include<cmath> #include<string> #include<vector> #include<bitset> #include<queue> #include<stack> #include<map> #include<set> using namespace std; #define Int long long #define V vector #define pii pair<int,int> #define ff first #define ss second mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pow2(x) (1LL<<(x)) #define msb(x) (63-__builtin_clzll(x)) #define bitcnt(x) (__builtin_popcountll(x)) #define nl '\n' #define _ << ' ' << #define all(x) (x).begin(), (x).end() #define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++) #define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush; const int N = 2e5+5; V<int> memo[N]; pii query(int i){ if(memo[i].empty()) memo[i] = ask(i); return {memo[i][0], memo[i][1]}; } int n; #define mid (tl+tr)/2 #define lc (v+1) #define rc (v+2*(mid-tl+1)) struct Segtree{ int cnt[2*N]; void upd(int i,int v=0,int tl=0,int tr=n-1){ if(tl==tr){ cnt[v] = 1; return; } if(i<=mid) upd(i, lc,tl,mid); else upd(i, rc,mid+1,tr); cnt[v] = cnt[lc] + cnt[rc]; } int qry(int l,int r,int v=0,int tl=0,int tr=n-1){ if(r<tl || tr<l) return 0; if(l<=tl && tr<=r) return cnt[v]; return qry(l,r, lc,tl,mid) + qry(l,r, rc,mid+1,tr); } } segtree; #undef mid int mx = 0; int dnc(int lout=0,int rout=0,int l=0,int r=n-1){ if(l > r) return -1; if(lout+rout+segtree.qry(l,r) == mx){ // assert(0); return -1; } int midcnt = 0; for(int m=(l+r)/2; m<=r; m++){ auto[lcnt,rcnt] = query(m); if(lcnt+rcnt==0) return m; if(lcnt+rcnt < mx){ midcnt++; continue; } if(lcnt > lout+midcnt){ int i = dnc(lout,midcnt+rcnt, l,(l+r)/2-1); if(i!=-1) return i; } if(rcnt > rout){ int i = dnc(lcnt,rout, m+1,r); if(i!=-1) return i; } return -1; } for(int m=(l+r)/2-1; m>=l; m--){ auto[lcnt,rcnt] = query(m); if(lcnt+rcnt==0) return m; if(lcnt+rcnt < mx){ midcnt++; continue; } // assert(rcnt == midcnt + rout); if(lcnt > lout){ int i = dnc(lout,rcnt, l,m-1); if(i!=-1) return i; } return -1; } return -1; } int find_best(int _n){ n = _n; V<int> ord; for(int i=0; i<min(n,237); i++){ ord.push_back(i); } for(int i=n-1; i>=max(n-237,0); i--){ ord.push_back(i); } rep(i,0,ord.size()){ swap(ord[i], ord[rng()%(i+1)]); } map<int,V<int>> mp; for(int j=0; j<ord.size(); j++){ int i = ord[j]; // for(int i=max(0,n/2-240); i<=min(n-1,n/2+240); i++){ // rep(i,0,474){ auto[lcnt,rcnt] = query(i); if(lcnt+rcnt==0) return i; mp[lcnt+rcnt].push_back(i); mx = max(mx, lcnt+rcnt); if(mp.size()==4) break; if(lcnt+rcnt>300) break; } assert((int)mp.size()<=4); for(auto&[x,v] : mp){ if(x==mx){ } else{ for(int i : v){ segtree.upd(i); } } } int ans = dnc(); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:132:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |  for(int j=0; j<ord.size(); j++){
      |               ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...