Submission #1155752

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

prize

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

    int ult=-1,pref=0;
    while(1)
    {
        int st=ult+1,dr=n-1,ans=-1;
        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;
            }
            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