Submission #739641

#	Time	Username	Problem	Language	Result	Execution time	Memory
739641		Charizard2021	The Big Prize (IOI17_prize)	C++17	100 / 100	60 ms	632 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;

map<int, pi> mp;

pi Ask(int x){
	if(mp.find(x) != mp.end()) return mp[x];
	auto q = ask(x);
	return mp[x] = pi(q[0], q[1]);
}

int find_best(int n) {
	if(n <= 5000){
		for(int i = 0; i < n; i++) {
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	vector<int> cp;
	for(int i=0; i<=500; i++){
		int w = ((n-1) * i) / 500;
		cp.push_back(w);
	}
	int thres = 0;
	for(auto &i : cp){
		pi p = Ask(i);
		thres = max(thres, p.first + p.second);
	}
	auto abnormal = [&](int x){
		pi p = Ask(x);
		return p.first + p.second != thres;
	};
	for(int i=0; i<n; i++){
		if(abnormal(i)){
			pi p = Ask(i);
			if(p.first + p.second == 0) return i;
		}
		else{
			auto incompatible = [&](int x, int y){
				assert(x < y);
				if(abnormal(y)) return true;
				auto p = Ask(x).second;
				auto q = Ask(y).second;
				return p != q;
			};
			int s = i + 1;
			int e = n + 100;
			for(auto &j : cp){
				if(j > i && incompatible(i, j)){
					e = j;
					break;
				}
				s = max(s, j);
			}
			while(s != e){
				int m = (s + e) / 2;
				if(incompatible(i, m)) e = m;
				else s = m + 1;
			}
			assert(abnormal(s));
			i = s - 1;
		}
	}
	assert(0);
}

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