Submission #946345

#	Time	Username	Problem	Language	Result	Execution time	Memory
946345		jay_jayjay	The Big Prize (IOI17_prize)	C++14	100 / 100	30 ms	3040 KiB

prize

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; };
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>

#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 42
#endif
#define ll long long
#define all(x) (x).begin(),(x).end()

#define mod int(1e9+7)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f

void sleep(int x) { this_thread::sleep_for(chrono::seconds(x)); }
struct { template<typename T> operator T() { T x; cin>>x; return x; } } in;

struct __rng {
        mt19937_64 _rng;
        __rng() {
                ll ctime = chrono::high_resolution_clock::now().time_since_epoch().count();
                _rng = mt19937_64(ctime);
        }
        
        ll randint(ll l, ll h) {
                return uniform_int_distribution<int>(l,h)(_rng);
        }
} rng;
// 1}}}
#define rank rank2
// #define DBG

#define N int(1e6)

vector<int> ask(int i);

#ifdef DBG
int n; vector<int> arr;
int pre[N][10], suf[N][10];
int q=0;
vector<int> ask(int i) {
        q++;
        // int l=0,r=0;
        // for(int j=0;j<i;j++)if(arr[j]<arr[i]) l++;
        // for(int j=i+1;j<n;j++)if(arr[j]<arr[i])r++;
        // assert(l == pre[i][arr[i]-1]);
        // assert(r == suf[i][arr[i]-1]);
        // return vector<int>{l,r};
        return vector<int>{pre[i][arr[i]-1],suf[i][arr[i]-1]};
}
#endif
int ans[N][2];
int best=-1;

void ask2(int i) {
        if(best == i) return;
        
        if(ans[i][0]+ans[i][1] == 0) {
                auto x = ask(i);
                ans[i][0] = x[0];
                ans[i][1] = x[1];
                if(ans[i][0]+ans[i][1] == 0) assert(best==-1), best &= i;
        }
}

int rank(int i) {
        ask2(i);
        return ans[i][0]+ans[i][1];
}

int right(int i) {
        ask2(i);
        return ans[i][1];
}



// lower rank is more rare
void solve(int l, int r) {
        if(best >= 0) return;
        if(r<l) return;
        if(l==r) return void(rank(l));
        while(rank(l) != rank(r)) {
                while(rank(l) < rank(r)) l++;
                while(rank(l) > rank(r)) r--;
        }
        if(right(l) == right(r)) return;
        
        int m=(l+r)/2;
        solve(l,m);
        solve(m,r);
}

int find_best(int n) {
        solve(0, n-1);
        assert(best >= 0);
        return best;
}

#ifdef DBG
int main() {
        n=in;arr.resize(n);for(auto&x:arr)x=in;
        for(int i=0;i<n;i++) {
                pre[i][arr[i]] = 1;
                suf[i][arr[i]] = 1;
        }
        for(int i=1;i<n;i++) for(int v=0;v<10;v++)pre[i][v]+=pre[i-1][v];
        for(int i=n-2;~i;i--)for(int v=0;v<10;v++)suf[i][v]+=suf[i+1][v];
        for(int i=0;i<n;i++)for(int v=1;v<10;v++)pre[i][v]+=pre[i][v-1], suf[i][v]+=suf[i][v-1];
        
        int ans = find_best(n);
        printf("%d\n",ans);
        printf("q=%d\n",q);
        return arr[ans]!=1;
}
#endif

Compilation message (stderr)

prize.cpp:22:73: warning: 'in' defined but not used [-Wunused-variable]
   22 | struct { template<typename T> operator T() { T x; cin>>x; return x; } } in;
      |                                                                         ^~

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