Submission #834871

#	Time	Username	Problem	Language	Result	Execution time	Memory
834871		Lobo	The Big Prize (IOI17_prize)	C++17	0 / 100	73 ms	952 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 = 970;
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<int> pos;
	for(int l = B; l < n; l+= S) {
		while(l < n && query(l).fr == query(lol.back()).fr) {
			esp.pb(l);
			if(query(l).fr == 0) return l;
			l++;
		}
		if(l >= n) break;
		int r = min(n-1,l+S-1);

		if(query(l) == query(r)) continue;

		// for(int i = l; i <= r; i++) {
		// 	pos.pb(i);
		// }
	}

	for(int i = B; i < n; i++) pos.pb(i);
 
	int i = 0;

	while(i < (int) pos.size()) {
		if(query(pos[i]).fr != query(lol.back()).fr) {
			esp.pb(pos[i]);
			if(query(pos[i]).fr == 0) return pos[i];
			i++;
			continue;
		}
 
		lol.pb(pos[i]);

		int l = i;
		int r = min((i/S+1)*S-1,(int) pos.size()-1);
		if(query(pos[r]).fr == 0) return pos[r];
		if(query(pos[i]).fr == query(pos[r]).fr && query(pos[i]).sc.fr == query(pos[r]).sc.fr) {
			i = r+1;
			continue;
		}
		int nx = -1;
		while(l <= r) {
			int mid = (l+r)/2;

			if(query(pos[mid]).fr == 0) return pos[mid];
 
			if(query(pos[mid]).fr != query(pos[i]).fr || query(pos[mid]).sc.fr != query(pos[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: 0 / 20
• Subtask 2: 0 / 80