Submission #960665

#	Time	Username	Problem	Language	Result	Execution time	Memory
960665		MarwenElarbi	The Big Prize (IOI17_prize)	C++17	100 / 100	27 ms	3104 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;
std::vector<int> ask(int i);

int ans[200005][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 rankk(int i) {
        ask2(i);
        return ans[i][0]+ans[i][1];
}
 
int right(int i) {
        ask2(i);
        return ans[i][1];
}
 
 
 
// lower rankk is more rare
void solve(int l, int r) {
        if(best >= 0) return;
        if(r<l) return;
        if(l==r) {
            rankk(l);
            return;
        }
        while(rankk(l) != rankk(r)) {
                while(rankk(l) < rankk(r)) l++;
                while(rankk(l) > rankk(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;
}

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