Submission #903244

#	Time	Username	Problem	Language	Result	Execution time	Memory
903244		JakobZorz	The Big Prize (IOI17_prize)	C++17	90 / 100	52 ms	612 KiB

prize

#include"prize.h"
#include<iostream>
#include<vector>
using namespace std;

int find_best(int n) {
    if(n<=5000){
        for(int i=0;i<n;i++){
            vector<int>res=ask(i);
            if(res[0]+res[1]==0)
                return i;
        }
    }
    
    int low=0;
    for(int i=0;i<500;i++){
        vector<int>res=ask(i);
        low=max(low,res[0]+res[1]);
    }
    
    int curr=0;
    while(curr<n){
        vector<int>res=ask(curr);
        if(res[0]+res[1]!=low){
            if(res[0]+res[1]==0)
                return curr;
            curr++;
            continue;
        }
        
        int l=curr,r=n;
        while(l<r-1){
            int mid=(l+r)/2;
            vector<int>res2=ask(mid);
            if(res2==res){
                l=mid;
            }else{
                r=mid;
            }
        }
        curr=r;
    }
    
	return 0;
}

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