Submission #1198942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198942		dosts	The Big Prize (IOI17_prize)	C++20	20 / 100	66 ms	9768 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<100;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) {
		if (pl <= 0) break;
		vector<int> q = ask(pl);
		vi prv = ask(pl-1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pl-1;
			while (ptr > 0) {
				prv = ask(ptr-1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr--;
				else break;
			}
			pl = ptr-1;
			continue;
		}
		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]+vv[1] != q[0]+q[1]) || (vv[1] > q[1])) l = m+1;
			else r = m-1;
		}
		for (int j = pl;j >= l;j--) possible.erase(j);
		pl = l;
	}
	while (1) {
		if (pr >= n-1) break;
		vector<int> q = ask(pr);
		vi prv = ask(pr+1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pr+1;
			while (ptr < n-1) {
				prv = ask(ptr+1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++;
				else break;
			}
			pr = ptr+1;
			continue;
		}
		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[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1;
			else l = m+1;
		}
		for (int j = pr;j <= r;j++) possible.erase(j);
		pr = 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