Submission #435811

#TimeUsernameProblemLanguageResultExecution timeMemory
435811OdaveyThe Big Prize (IOI17_prize)C++17
20 / 100
141 ms10312 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #define MX_N 200005 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int #include "prize.h" int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; int tipe[MX_N]; int N; bitset<MX_N> in_cache; pair<int, int> cache[MX_N]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //vector<int> ask(int i){ // vector<int> res = {0, 0}; // for(int j=i+1;j<N;++j){ // res[1] += (tipe[j] < tipe[i]); // } // for(int j=0;j<i;++j){ // res[0] += (tipe[j] < tipe[i]); // } // return res; //} pair<int, int> query(int i){ if(!in_cache[i]){ auto res = ask(i); cache[i].fi = res[0]; cache[i].se = res[1]; } in_cache[i] = 1; return cache[i]; } set<int> pos[MX_N]; int find_best(int n){ uniform_int_distribution<> Id(0, n-1); in_cache.set(); in_cache.flip(); if(n < 5000){ for(int i=0;i<n;++i){ auto [L, R] = query(i); if(L == 0 && R == 0){ return i; } } } int best = 1000000009; set<int> candidates; while(candidates.size() < 50){ int i = Id(rng); auto [L, R] = query(i); if(L == 0 && R == 0){ return i; } candidates.insert(i); pos[L+R].insert(i); if(pos[L+R].size() >= 2){ best = min(best, L+R); } } while(best != 0){ vector<pair<double, pair<int, int> > > options; int last = -1; int final_pos = *(pos[best].end()); for(int i : pos[best]){ double rho = 0.0; if(i == 0){ rho = 0.0; last = i; continue; } if(last == -1){ rho += (double)query(i).fi; rho /= (double)i; options.pb(make_pair(rho, make_pair(last, i))); last = i; continue; } if(last+1 == i){ rho = 0.0; last = i; continue; } rho += (double)(query(i).fi - query(last).fi); rho /= (double)(i-last-1); options.pb(make_pair(rho, make_pair(last, i))); last = i; } if(last+1 != n){ double rho = 0.0; rho += (double)query(last).se; rho /= (double)(n-last-1); options.pb(make_pair(rho, make_pair(last, n))); } sort(All(options)); reverse(All(options)); bool best_update = false; for(auto pp : options){ if(best_update){ break; } int lo = pp.se.fi; int hi = pp.se.se; int in_range; if(lo == -1){ in_range = query(hi).fi; }else if(hi == n){ in_range = query(lo).se; }else{ in_range = query(hi).fi - query(lo).fi; } while(in_range > 0){ int r = hi - lo - 1; int i = lo + 1 + (Id(rng)%r); auto [L, R] = query(i); if(L == 0 && R == 0){ return i; } if(L+R == best){ double rhoL = 0.0, rhoR = 0.0; if(lo == -1){ if(i == 0){ rhoL = 0.0; }else{ rhoL = L; rhoL /= (double)(i); } }else{ if(lo+1 == i){ rhoL = 0.0; }else{ rhoL = L - query(lo).fi; rhoL /= (double)(i-lo-1); } } if(hi == n){ if(i == n-1){ rhoR = 0.0; }else{ rhoR = R; rhoR /= (double)(n-i-1); } }else{ if(i+1 == hi){ rhoR = 0.0; }else{ rhoR = query(hi).fi - L; rhoR /= (double)(hi-i-1); } } if(rhoR > rhoL){ lo = i; }else{ hi = i; } }else if(L+R < best){ pos[L+R].insert(i); in_range--; if(pos[L+R].size() >= 2){ best = L+R; best_update = true; break; } } } } } }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:101:13: warning: unused variable 'final_pos' [-Wunused-variable]
  101 |         int final_pos = *(pos[best].end());
      |             ^~~~~~~~~
prize.cpp:84:14: warning: control reaches end of non-void function [-Wreturn-type]
   84 |     set<int> candidates;
      |              ^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...