Submission #90011

#	Time	Username	Problem	Language	Result	Execution time	Memory
90011		nikolapesic2802	The Big Prize (IOI17_prize)	C++14	20 / 100	92 ms	716 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;


int find_best(int n) {
    int N=2e5+5;
    int lo=(int)sqrt(N);
    int maxx=0;
    for(int i=0;i<lo;i++)
    {
        vector<int> tr=ask(i);
        int t=tr[0]+tr[1];
        if(t==0)
            return i;
        maxx=max(maxx,t);
    }
    int nasao=0;
    int last=0;
    while(true)
    {
        int l=last,r=n-1;
        while(l<r)
        {
            int m=(l+r)>>1;
            vector<int> tr=ask(m);
            int t=tr[0]+tr[1];
            if(t==0)
                return m;
            if(t!=maxx)
            {
                r=m;
                continue;
            }
            if(tr[0]>nasao)
                r=m-1;
            else
                l=m+1;
        }
        vector<int> tr=ask(l);
        int t=tr[0]+tr[1];
        if(t==0)
            return l;
        last=l+1;
        nasao++;
    }
}

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