Submission #833077

#	Time	Username	Problem	Language	Result	Execution time	Memory
833077		Lobo	The Big Prize (IOI17_prize)	C++17	0 / 100	92 ms	884 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;

pair<int,pair<int,int>> query(int i) {
	if(qr.count(i)) return qr[i];
	vector<int> perg = ask(i);
	return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}

const int B = 500;
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++;
		}

		lol.pb(i);

		int l = i;
		int r = n-1;
		int nx = -1;
		while(l <= r) {
			int mid = (l+r)>>1;

			if(query(mid).fr != query(i).fr || query(mid).sc.fr != query(i).sc.fr) {
				r = mid-1;
			}
			else {
				nx = i;
				l = mid+1;
			}
		}

		i = nx+1;
	}


	for(auto i : esp) {
		if(query(i).fr == 0) return i;
	}
	assert(false);
	return -1;
}

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