Submission #420177

#	Time	Username	Problem	Language	Result	Execution time	Memory
420177		oolimry	The Big Prize (IOI17_prize)	C++17	100 / 100	97 ms	10300 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;
vector<int> memo[200005];
bool isgood[200005];
bool tried[200005];
 
void dnc(vector<int> stuff, int good, int Lgood, int Rgood){
	if(good == 0) return;
	if(sz(stuff) == 0) return;
	//show3(good,Lgood,Rgood);
	
	int cnt = 0;
	int m = sz(stuff)/2;
	vector<int> S;
	for(int i = 0;i < sz(stuff);i++){
		int x = stuff[i];
		if(tried[x] and not isgood[x]) S.push_back(i);
		if(tried[x] and isgood[x]) cnt++;
	}
	
	if(sz(S) > 0) m = S[sz(S)/2];
	
	int orim = m;
		
	while(m < sz(stuff)){
		vector<int> res;
		if(tried[stuff[m]]) res = memo[stuff[m]];
		else 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) - orim;
	for(int i = 0;i < orim;i++) L.push_back(stuff[i]);
	dnc(L, good-btwgood, Lgood, Rgood+btwgood);
}
 
int find_best(int n) {
	srand(12345);
	int taken = 0;
	while(taken < min(n, 500)){
		int i = rand()%n;
		if(tried[i]) continue;
		
		tried[i] = 1;
		vector<int> res = ask(i);
		memo[i] = res;
		worst = max(worst,res[0]+res[1]); 
		if(res[0]+res[1] == 0) ans = i;
		taken++;
	}
	
	if(ans != -1) return ans;
	
	for(int i = 0;i < n;i++){
		if(tried[i]) isgood[i] = (memo[i][0]+memo[i][1] != worst);
	}
	
	vector<int> v;
	for(int i = 0;i < n;i++){
		v.push_back(i);
	}
	dnc(v, worst, 0, 0);
	
	return ans;
}

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