Submission #600920

#	Time	Username	Problem	Language	Result	Execution time	Memory
600920		Lucpp	The Big Prize (IOI17_prize)	C++17	90 / 100	106 ms	1820 KiB

prize

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

int MAX = 500;

map<int, vector<int>> memo;
vector<int> qry(int i){
	if(memo.count(i)) return memo[i];
	vector<int> a = ask(i);
	return memo[i] = a;
}

int find_best(int n) {
	MAX = min(n, MAX);
	int v = 0;
	for(int i = 0; i < MAX; i++){
		vector<int> a = qry(i);
		if(a[0] + a[1] == 0) return i;
		v = max(v, a[0]+a[1]);
	}
	vector<int> pos;
	for(int i = MAX; i < n; i++) pos.push_back(i);
	vector<pair<int, int>> found;
	for(int i = 0; i < MAX; i++){
		vector<int> a = qry(i);
		if(a[0] + a[1] < v) found.emplace_back(i, a[0]+a[1]);
	}
	while(true){
		int lo = 0, hi = (int)pos.size()-1;
		for(int mid = (lo+hi)/2; lo <= hi; mid=(lo+hi)/2){
			int p = pos[mid];
			vector<int> a = qry(p);
			if(a[0]+a[1] == 0) return p;
			if(a[0]+a[1] != v){
				found.emplace_back(p, a[0]+a[1]);
				pos.erase(pos.begin()+mid);
				break;
			}
			int cnt = 0;
			for(auto [i, x] : found){
				if(i < p && x < v) cnt++;
			}
			if(cnt < a[0]) hi = mid-1;
			else lo = mid+1;
		}
	}
	return -1;
}

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