Submission #931924

#	Time	Username	Problem	Language	Result	Execution time	Memory
931924		Lobo	The Big Prize (IOI17_prize)	C++17	100 / 100	33 ms	2004 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;
	vector<int> perg = ask(i);
	return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
 
int find_best(int N) {
 	n = N;
 	if(n <= 5000) {
 		for(int i = 0; i < n; i++) {
 			if(query(i).fr == 0) return i;
 		}
 	}
 	int S = n/420;
 	priority_queue<pair<pair<int,int>,pair<int,int>>> q;

 	for(int i = 0; i*S < n; i++) {
 		// i*S,(i+1)*S
 		int l = i*S;
 		int r = min(n-1,(i+1)*S);

		q.push(mp(mp(0,query(r).sc.fr-query(l).sc.fr),mp(l,r)));
 	}

 	while(q.size()) {
 		int l = q.top().sc.fr;
 		int r = q.top().sc.sc;
 		q.pop();
 		if(l > r) continue;

 		if(query(l).fr == 0) return l;
 		if(query(r).fr == 0) return r;
 		if(r-l+1 <= 2) continue;

 		if(query(l) == query(r)) continue;
 		int mid = (l+r)/2;
 		if(l <= mid) q.push(mp(mp(0,query(mid).sc.fr-query(l).sc.fr),mp(l,mid)));
 		if(mid <= r) q.push(mp(mp(0,query(r).sc.fr-query(mid).sc.fr),mp(mid,r)));

 		// int ml = (2*l+r)/3;
 		// int mr = (l+2*r)/3;
 		// q.push(mp(l,ml));
 		// q.push(mp(ml,mr));
 		// q.push(mp(mr,r));
 	}

 	assert(false);
 	return -1;


}

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