제출 #1271895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271895		Aviansh	커다란 상품 (IOI17_prize)	C++20	20 / 100	15 ms	604 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>

using namespace std;

int find_best(int n) {
    int cutoff = 0;
    int lef = 0;
    int ind = -1;
	for(int i = 0; i < min(n,460); i++) {
		vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
        if(cutoff<res[0]+res[1]) {
            cutoff=res[0]+res[1];
            ind=i;
            lef=res[0];
        }
	}
    bool val[n];
    fill(val,val+n,0);
    int cn = 0;
    while(1){
        int lo = ind;
        int hi = min(n-1,lo+1023);
        while(lo<hi){
            int mid = (lo+hi+1)/2;
            vector<int>res = ask(mid);
            if(res[0]+res[1]==0){
                return mid;
            }
            if(res[0]==lef&&res[0]+res[1]==cutoff){
                lo=mid;
            }
            else{
                hi=mid-1;
            }
        }
        fill(val+ind,val+lo+1,1);
        ind=lo;
        while(++ind<n){
            cn++;
            assert(cn<=1000);
            vector<int>res = ask(ind);
            lef=res[0];
            if(res[0]+res[1]==cutoff){
                break;
            }
            if(res[0]+res[1]==0){
                return ind;
            }
        }
        if(ind==n){
            break;
        }
    }
	return -1;
}

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