Submission #435836

#	Time	Username	Problem	Language	Result	Execution time	Memory
435836		Odavey	The Big Prize (IOI17_prize)	C++17	20 / 100	119 ms	10824 KiB

prize

//
// ~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 <= 50){
        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;
        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:84:14: warning: control reaches end of non-void function [-Wreturn-type]
   84 |     set<int> candidates;
      |              ^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80