제출 #834841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834841		Lobo	커다란 상품 (IOI17_prize)	C++17	90 / 100	84 ms	788 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;
int cntnonlol;
int n;
pair<int,pair<int,int>> query(int i) {
	if(i == n) return mp(cntnonlol,mp(cntnonlol,0));
	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 = 600;
int find_best(int N) {
 	n = N;
	vector<int> esp,lol;
	lol.pb(0);
	query(0);
	for(int i = 1; i < min(n,B); i++) {
		if(query(i).fr == 0) return i;
		if(query(i).fr > query(lol.back()).fr) {
			for(auto x : lol) {
				if(query(x).fr == 0) return x;
				esp.pb(x);
			}
			lol.clear();
			lol.pb(i);
		}
		else {
			esp.pb(i);
			if(query(i).fr == 0) return i;
		}
	}

	cntnonlol = query(lol.back()).fr;

	vector<pair<int,int>> lr;
	for(int l = B; l < n; l+= S) {
		lr.pb(mp(l,min(l+S-1,n-1)));
	}

	while(lr.size()) {
		int l = lr.back().fr;
		int r = lr.back().sc;
		lr.pop_back();

		while(l <= r && query(l).fr != query(lol.back()).fr) {
			if(query(l).fr == 0) return l;
			esp.pb(l);
			l++;
		}

		while(l <= r && query(r).fr != query(lol.back()).fr) {
			if(query(r).fr == 0) return r;
			esp.pb(r);
			r--;
		}

		if(l > r) continue;
		if(query(l).sc.fr == query(r).sc.fr) continue;

		int mid = (l+r)/2;
		lr.pb(mp(l,mid));
		lr.pb(mp(mid+1,r));
	}


 
	// 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