제출 #903375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
903375		JakobZorz	커다란 상품 (IOI17_prize)	C++17	93.91 / 100	33 ms	2936 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.first+res2.second!=low){
                curr=mid;
                while(curr>=0){
                    auto res3=query(curr);
                    s.insert({curr,res3});
                    if(res3.first+res3.second==0)
                        return curr;
                    if(res3.first+res3.second==low){
                        curr++;
                        break;
                    }
                    curr--;
                }
                curr=l;
                break;
            }
            
            if(res2==res)
                l=mid;
            else
                r=mid;
        }
        if(l==r-1)
            curr=r;
    }
    
	return -1;
}

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