Submission #1199741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199741		Aviansh	The Big Prize (IOI17_prize)	C++20	90 / 100	26 ms	2004 KiB

prize

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

using namespace std;

vector<int> reduce(vector<int>inds){
    if(inds.size()<=1000){
        //iterate
        for(int i : inds){
            vector<int>quer = ask(i);
            if(quer[0]==quer[1]&&quer[0]==0){
                vector<int>ans;
                ans.push_back(i);
                return ans;
            }
        }
    }
    int n = inds.size();
    int cutoff = 0;
    for(int i = 0;i<min(n,600);i++){
        vector<int>quer = ask(inds[i]);
        cutoff=max(cutoff,quer[0]+quer[1]);
        if(quer[0]+quer[1]==0){

        }
    }
    //cout << "iterating\n";
    //must query among inds and remove worst one and return inds of all that are strictly not greatest in this one
    int lo = 0;
    int hi = inds.size();
    set<int>smaller;
    while(1){
        lo=0;
        if(smaller.size()){
            lo=*(--smaller.end())+1;
        }
        hi=inds.size();
        while(lo<hi){
            int mid = (lo+hi)/2;
            //cout << inds[lo] << " " << inds[mid] << " " << inds[hi] << "\n";
            vector<int>quer = ask(inds[mid]);
            if(quer[0]+quer[1]<cutoff){
                //cout << "hi=mid1\n";
                hi=mid;
            }
            else if(quer[0]>smaller.size()){
                //cout << "hi=mid2\n";
                hi=mid;
            }
            else{
                //cout << "lo=mid+1\n";
                lo=mid+1;
            }
        }
        if(lo==inds.size())
            break;
        int sz = smaller.size();
        smaller.insert(inds[lo]);
        if(sz==smaller.size()){
            break;
        }
        //cout << "added: " << inds[lo] << "\n";
    }
    vector<int>ans;
    for(int i : smaller){
        ans.push_back(i);
    }
    return ans;
}

int find_best(int n) {
    vector<int>inds(n);
    iota(inds.begin(),inds.end(),0);
    while(inds.size()>1){
        inds=reduce(inds);
    }
    return inds[0];
}

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