Submission #835876

#	Time	Username	Problem	Language	Result	Execution time	Memory
835876		oscar1f	The Big Prize (IOI17_prize)	C++17	100 / 100	72 ms	33520 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
 
using namespace std;
 
const int MAX_VAL=200*1000+5;
int nbVal,nbPasMax,rep=-1;
set<int> memeSom[MAX_VAL]; 
vector<int> ans[MAX_VAL];

void calc(int deb,int fin) {
	if (fin<deb or rep!=-1) {
		return;
	}
	int mid=(deb+fin)/2;
	ans[mid]=ask(mid);
	int som=ans[mid][0]+ans[mid][1];
	if (som==0) {
		rep=mid;
	} 
	memeSom[som].insert(mid);
	auto it=memeSom[som].upper_bound(mid);
	if ((*it)==MAX_VAL or ans[mid][0]!=ans[(*it)][0]) {
		calc(mid+1,fin);
	}
	it=memeSom[som].lower_bound(mid);
	it--;
	if ((*it)==-MAX_VAL or ans[mid][0]!=ans[(*it)][0]) {
		calc(deb,mid-1);
	}
}
 
int find_best(int n) {
	nbVal=n;
	for (int i=0;i<nbVal;i++) {
		memeSom[i].insert(MAX_VAL);
		memeSom[i].insert(-MAX_VAL);
	}
	calc(0,nbVal-1);
	return rep;
}

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