Submission #1198937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198937		dosts	The Big Prize (IOI17_prize)	C++20	20 / 100	55 ms	9780 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int inf = 2e9;
int find_best(int n) {
	set<int> possible;
	int mx = 0;
	srand(time(0));
	int select;
	for (int i = 0;i<50;i++) {
		int r = rand()%n;
		vi g = ask(r);
		if (g[0]+g[1] > mx) {
			mx = g[0]+g[1];
			select = r;
		}
		if (g[0]+g[1] == 0) return r;
	}
	for (int i=0;i<n;i++) possible.insert(i);
	int pl = select,pr = select;
	while (1) {
		vector<int> q = ask(pl);
		int l = 0;
		int r = pl-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = ask(m);
			if (vv[0]+vv[1] == 0) return m;
			if (vv[0] < q[0]) l = m+1;
			else r = m-1;
		}
		if (r == -1) break;
		possible.erase(r);
		pl = r;
	}
	while (1) {
		vector<int> q = ask(pr);
		int l = pr+1;
		int r = n-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = ask(m);
			if (vv[0]+vv[1] == 0) return m;
			if (vv[1] < q[1]) r = m-1;
			else l = m+1;
		}
		if (l == n) break;
		possible.erase(l);
		pl = r;
	}
	for (auto it : possible) {
		vi vv = ask(it);
		if (vv[0] + vv[1] == 0) return it;
	}
	assert(0);
}

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