Submission #610970

#	Time	Username	Problem	Language	Result	Execution time	Memory
610970		Apiram	The Big Prize (IOI17_prize)	C++14	100 / 100	47 ms	528 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
int find_best(int n) {
	int ans = -1;
	int rejectedright = n,rejectedleft = -1;
	queue<pair<int,int>>q;
	q.push({0,n - 1});
	map<int,set<pair<int,int>>>pq;
	while(!q.empty()){
		auto u = q.front();
		q.pop();
		int left = u.first,right = u.second;
		if (left > right)continue;
		if (left >=rejectedright)continue;
		if (right<=rejectedleft)continue;
		if (right > rejectedright){
			q.push({left,rejectedright - 1});
			continue;
		}
		if (left < rejectedleft){
			q.push({rejectedleft + 1,right});
			continue;
		}
		if (left == right){
			vector<int>res = ask(left);
			pq[res[0] + res[1]].insert(make_pair(left,res[1]));
			if (res[0] + res[1] == 0){
				ans = left;
				break;
			} 
			continue;
		}
		int mid = (left + right)>>1;
		vector<int>res = ask(mid);
		pq[res[0] + res[1]].insert(make_pair(mid,res[1]));
		if (res[0] + res[1] == 0){
			ans = mid;
			break;
		}
		auto it = pq[res[0] + res[1]].find(make_pair(mid,res[1]));
		if (res[0] > 0){
			bool ok = true;
			if (it != pq[res[0] + res[1]].begin()){
				auto it2 = *prev(it);
				if (it2.second - res[1] <=0)ok = false;
			}
			if (ok){
				q.push({left,mid - 1});
			}
			else{
				//rejectedleft = max(rejectedleft,mid);
			}
		}
		else{
			rejectedleft = max(rejectedleft,mid);
		}
		if (res[1] > 0){
			bool ok = true;
			if (next(it)!=pq[res[0] + res[1]].end()){
				auto it2 = *next(it);
				if (res[1] - it2.second <=0)ok = false;
			}
			if (ok){
				q.push({mid + 1,right});
			}
			else{
				//rejectedright = min(rejectedright,mid);
			}
		}
		else{
			rejectedright = min(rejectedright,mid);
		}
	}
	return ans;
}

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