제출 #834573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834573		Lobo	커다란 상품 (IOI17_prize)	C++17	90 / 100	80 ms	740 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
map<int,pair<int,pair<int,int>>> qr;
 
int cnt = 0;
pair<int,pair<int,int>> query(int i) {
	if(qr.count(i)) return qr[i];
	++cnt;
	// assert(cnt <= 8500);
	vector<int> perg = ask(i);
	return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
 
const int B = 477;
const int S = 400;
int find_best(int n) {
 
	vector<int> esp,lol;
	lol.pb(0);
	query(0);
	for(int i = 1; i < min(n,B); i++) {
		if(query(i).fr > query(lol.back()).fr) {
			for(auto x : lol) esp.pb(x);
			lol.clear();
			lol.pb(i);
		}
		else {
			esp.pb(i);
		}
	}
 
	int i = B;

	while(i < n) {
		if(query(i).fr != query(lol.back()).fr) {
			esp.pb(i);
			i++;
			continue;
		}
 
		lol.pb(i);

		int l = i;
		int r = min(i+S-1,n-1);
		if(query(i).fr == query(r).fr && query(i).sc.fr == query(r).sc.fr) {
			i = r+1;
			continue;
		}
		int nx = -1;
		while(l <= r) {
			int mid = (l+r)/2;
 
			if(query(mid).fr != query(i).fr || query(mid).sc.fr != query(i).sc.fr) {
				r = mid-1;
			}
			else {
				nx = mid;
				l = mid+1;
			}
		}
 
		i = nx+1;
	}
 
 
	for(auto i : esp) {
		if(query(i).fr == 0) return i;
	}
	assert(false);
	return -1;
}

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