Submission #134530

#	Time	Username	Problem	Language	Result	Execution time	Memory
134530		dvdg6566	The Big Prize (IOI17_prize)	C++14	100 / 100	64 ms	1648 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()

int MAXQ = 0;
vi nextrow,cur;
vi currow;

void dnc(int s, int e, int loff, int roff){
	if (s > e)return;
	// cout<<"DNC "<<s<<' '<<e<<' '<<loff<<' '<<roff<<'\n';
	if (loff + roff == MAXQ)return; // None exist in this range
	if (s == e){
		nextrow.pb(currow[s]);
		return;
	}

	int m = (s+e)/2;
	int done=0;

	while(m<=e){
		cur = ask(currow[m]);
		// cout<<"Query "<<m<<' '<<cur[0]<<' '<<cur[1]<<'\n';
		if (cur[0]+cur[1] == MAXQ)break;
		nextrow.pb(currow[m]);
		++done;
		++m;
	}
	pi x = mp(cur[0],cur[1]);
	int lm = (s+e)/2;
	dnc(s,lm-1,loff,x.s+done);
	dnc(m+1,e,x.f,roff);
}

int find_best(int n) {
	for (int i=0;i<n;++i)currow.pb(i);
	while(1){
		MAXQ = 0;
		for (int i=0;i<sqrt(SZ(currow))+sqrt(sqrt(SZ(currow))) + 3&&i<SZ(currow);++i){
			vi x = ask(currow[i]);
			MAXQ = max(MAXQ, x[0] + x[1]);
		}
		// cout<<MAXQ<<'\n';
		dnc(0,SZ(currow)-1,0,0);
		// for (auto i : nextrow)cout<<i<<' ';cout<<'\n';
		// if (SZ(nextrow) == 2)break;
		sort(ALL(nextrow));
		if(SZ(nextrow) == 1)return nextrow[0];
		swap(nextrow,currow);
		nextrow.clear();
	}


	return 0;
}

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