Submission #420080

#	Time	Username	Problem	Language	Result	Execution time	Memory
420080		oolimry	The Big Prize (IOI17_prize)	C++17	20 / 100	113 ms	4528 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef unsigned long long lint;
typedef pair<lint,lint> ii;

int ans = -1;
int worst = 0;
void dnc(vector<int> stuff, int good, int Lgood, int Rgood){
	if(good == 0) return;
	if(sz(stuff) == 0) return;
	
	int m = sz(stuff)/2;
	int orim = m;
	while(m < sz(stuff)){
		auto res = ask(stuff[m]);
		if(res[0]+res[1] == 0) ans = stuff[m];
		
		if(res[0]+res[1] == worst){
			vector<int> L, R;
			for(int i = 0;i < orim;i++) L.push_back(stuff[i]);
			for(int i = m+1;i < sz(stuff);i++) R.push_back(stuff[i]);
			
			int btwgood = m-orim;
			
			dnc(L, res[0]-Lgood-btwgood, Lgood, res[1]+btwgood);
			dnc(R, res[1]-Rgood-btwgood, res[0]+btwgood, Rgood);
			return;
		}
		else m++;
	}
	
	vector<int> L;
	int btwgood = sz(stuff) - m;
	for(int i = 0;i < orim;i++) L.push_back(stuff[i]);
	dnc(L, good-btwgood, Lgood, Rgood+btwgood);
}

int find_best(int n) {
	for(int i = 0;i < min(450,n);i++){
		auto res = ask(i);
		worst = max(worst,res[0]+res[1]); 
	}
	
	vector<int> v(n);
	for(int i = 0;i < n;i++) v[i] = i;
	dnc(v, worst, 0, 0);
	
	return ans;
}

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