Submission #828685

#	Time	Username	Problem	Language	Result	Execution time	Memory
828685		gromperen	The Big Prize (IOI17_prize)	C++14	0 / 100	22 ms	11996 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
vector<int> p;
vector<vector<int>> memo(MAXN, vector<int>(2, -1));
vector<int> _ask(int i) {
	if (memo[i][0] != -1) return memo[i];
	return memo[i] = ask(p[i]);
}

int find_best(int n) {
	int mx = 0;
	int sqrtn = sqrt(n);
	p.resize(n);
	for (int i = 0; i < n; ++i) {
		p[i] = i;
	}
	srand(420);
	random_shuffle(p.begin(), p.end());
	int k = 0;
	for(int i = 0; i < sqrtn; i++) {
		vector<int> res = _ask(i);
		if(res[0] + res[1] == 0) return p[i];
		mx = max(mx, res[0] + res[1]);
	}
	for (int i = sqrtn; i < n; ++i) {
		auto res = _ask(i);
		if (res[0] + res[1] < mx) {
			if (res[0] + res[1] == 0) return p[i];
			continue;
		}
		int l = i, r = n-1;
		int tmp = i;
		while(l<r) {
			int mid = (l+r)/2;
			auto rmid = _ask(mid);
			if (rmid[0]+rmid[1] < mx || rmid[1] < res[1]) {
				if (rmid[0]+rmid[1] == 0) return p[mid];
				r = mid;
			} else {
				l = mid+1;
				tmp = mid;
			}
		}
		i = tmp;
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:23:6: warning: unused variable 'k' [-Wunused-variable]
   23 |  int k = 0;
      |      ^

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