Submission #960658

#	Time	Username	Problem	Language	Result	Execution time	Memory
960658		MarwenElarbi	The Big Prize (IOI17_prize)	C++17	90 / 100	57 ms	608 KiB

prize

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

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

int find_best(int n){
    int bg=0;
    int cnt=0;
    for (int i = 0; i < min(480,n); ++i)
    {
        vector<int> cur=ask(i);
        if(cur[0]==0&&cur[1]==0) return i;
        if(cnt<=cur[0]+cur[1]){
            cnt=max(cnt,cur[0]+cur[1]);
            bg=i;
        }
    }
    bool vis[n];
    memset(vis,0,sizeof vis);
    while(true){
        //return 0;
        int l=bg;
        int r=n;
        //cout <<l<<endl;
        vector<int> fir=ask(l);
        while(r-l>1){
            int mid=(r+l)/2;
            vector<int> cur=ask(mid);
            vis[mid]=true;
            if(cur[0]==0&&cur[1]==0) return mid;
            if(cur[0]+cur[1]!=cnt){
                r=mid;
                continue;
            }
            if(cur[1]+fir[0]!=cnt) r=mid;
            else {
                l=mid;
            }
        }
        bg=l+1;
        while(vis[bg]) bg++;
        fir=ask(bg);
        if(fir[0]==0&&fir[1]==0) return bg;
        while(fir[0]+fir[1]!=cnt){
            bg++;
            if(vis[bg]) continue;
            fir=ask(bg);
            if(fir[0]==0&&fir[1]==0) return bg;
        }
    }
    return n-1;
}

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