Submission #903389

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

prize

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

bool dpt[200000];
pair<int,int>dp[200000];

pair<int,int>query(int i){
    if(dpt[i])
        return dp[i];
    dpt[i]=true;
    auto res=ask(i);
    dp[i]={res[0],res[1]};
    return dp[i];
}

int find_best(int n) {
    if(n<=5000){
        for(int i=0;i<n;i++){
            auto res=query(i);
            if(res.first+res.second==0)
                return i;
        }
    }
    
    const int FIRST=500;
    
    int low=0;
    for(int i=0;i<FIRST;i++){
        auto res=query(i);
        if(res.first+res.second==0)
            return i;
        low=max(low,res.first+res.second);
    }
    
    set<pair<int,pair<int,int>>>s;
    
    int curr=FIRST;
    while(curr<n){
        auto res=query(curr);
        if(res.first+res.second==0)
            return curr;
        
        /*if(res.first+res.second!=low){
            curr++;
            continue;
        }*/
        
        int l=curr,r=n-1;
        while(!s.empty()){
            auto b=*s.begin();
            if(b.first<=curr){
                s.erase(s.begin());
                continue;
            }
            
            if(b.second==res){
                l=b.first;
                s.erase(s.begin());
                continue;
            }else{
                r=b.first;
                s.erase(s.begin());
                break;
            }
        }
        
        while(l<r-1){
            int mid=(l+r)/2;
            auto res2=query(mid);
            if(res2.first+res2.second==0)
                return mid;
            s.insert({mid,res2});
            
            if(res2==res)
                l=mid;
            else
                r=mid;
        }
        if(l==r-1)
            curr=r;
    }
    
	return -1;
}

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