Submission #299723

#	Time	Username	Problem	Language	Result	Execution time	Memory
299723		errorgorn	The Big Prize (IOI17_prize)	C++14	98.12 / 100	59 ms	3192 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(42069);

const int CHECK=447;
ii memo[200005];

ii get(int i){
	if (memo[i]!=ii(-1,-1)) return memo[i];
	
	auto temp=ask(i);
	return memo[i]=ii(temp[0],temp[1]);
}

int mx;
vector<int> good;

void dnc(int l,int r,int i,int j){
	//rep(x,0,100000000) ;
	//cout<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
	
	if (r<l) return;
	if (i==j) return;
	
	int m=l+r>>1;
	int m2=m;
	while (m2<=r && get(m2).fi+get(m2).se!=mx){
		good.push_back(m2);
		m2++;
	}
	
	if (m2>r) dnc(l,m-1,i,j-(m2-m));
	else{
		auto temp=get(m2);
		dnc(l,m-1,i,temp.fi-(m2-m));
		dnc(m2+1,r,temp.fi,j);
	}
}

int find_best(int n) {
	memset(memo,-1,sizeof(memo));
	
	vector<int> pos;
	rep(x,0,n) pos.push_back(x);
	
	rep(x,0,n) swap(pos[x],pos[rng()%(x+1)]);
	
	rep(x,0,min(n,CHECK)){
		auto temp=get(pos[x]);
		mx=max(mx,temp.fi+temp.se);
	}
	
	dnc(0,n-1,0,mx);
	
	//for (auto &it:good) cout<<it<<" "; cout<<endl;
	
	for (auto &it:good){
		if (get(it)==ii(0,0)) return it;
	}
	
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'void dnc(int, int, int, int)':
prize.cpp:37:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |  int m=l+r>>1;
      |        ~^~

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