제출 #903264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
903264		JakobZorz	커다란 상품 (IOI17_prize)	C++17	0 / 100	1 ms	608 KiB

prize

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

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

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=100;
    
    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);
    }
    
    int curr=FIRST;
    while(curr<n){
        auto res=query(curr);
        if(res.first+res.first==0)
            return curr;
        
        if(res.first+res.first!=low){
            curr++;
            continue;
        }
        
        int l=curr,r=n;
        while(l<r-1){
            int mid=(l+r)/2;
            auto res2=query(mid);
            if(res2.first+res2.first==0)
                return curr;
            
            if(res2==res)
                l=mid;
            else
                r=mid;
        }
        curr=r;
    }
    
	return -1;
}

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