Submission #1155764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155764		alexdd	The Big Prize (IOI17_prize)	C++20	90 / 100	19 ms	2000 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> asked;
int cate;
pair<int,int> query(int x)
{
    if(asked[x].first==-1)
    {
        vector<int> cv = ask(x);
        asked[x] = {cv[0],cv[1]};
        cate = max(cate, cv[0] + cv[1]);
    }
    return asked[x];
}
mt19937 rnd(time(0));
int find_best(int n)
{
    asked.resize(n,{-1,-1});
    /*for(int pas=0;pas<1000;pas++)
    {
        int x = rnd()%n;
        query(x);
    }*/

    int ult=-1,pref=0;
    query(0);
    set<int> bune;
    while(1)
    {
        auto it = bune.upper_bound(ult);
        if(it != bune.end())
        {
            int x = (*it) - 1;
            if(query(x).first + query(x).second == cate && query(x).first == pref)
            {
                pref++;
                ult = x;
                continue;
            }
        }
        int st=ult+1,dr=n-1,ans=-1;
        //query(st);
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(query(mij).first + query(mij).second < cate || query(mij).first > pref)
            {
                ans = mij;
                dr = mij-1;
                if(query(ans).first + query(ans).second == 0)
                    return ans;
                if(query(mij).first + query(mij).second < cate)
                {
                    bune.insert(mij);
                }
            }
            else
                st = mij+1;
        }
        if(ans==-1)
            break;
        if(query(ans).first + query(ans).second == 0)
            return ans;
        pref++;
        ult = ans;
    }
    assert(0);
    return 0;
}

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