Submission #593814

#	Time	Username	Problem	Language	Result	Execution time	Memory
593814		AlperenT	The Big Prize (IOI17_prize)	C++17	20 / 100	78 ms	424 KiB

prize

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

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int int_rand(int a, int b){
	return uniform_int_distribution<int>(a, b)(rng);
}

const int TRYMAX = 10, K = 500;

int maxcnt = 0;

int find_best(int n){
	for(int i = 0; i < TRYMAX; i++){
		vector<int> vec = ask(int_rand(0, n - 1));

		maxcnt = max(maxcnt, vec[0] + vec[1]);
	}

	vector<bool> ismax(n, false);

	int pos = 0, prefix = 0;

	while(pos < n){
		vector<int> vec = ask(pos);

		if(vec[0] + vec[1] != maxcnt) pos++;

		int l = pos - 1, r = min(pos + K, n);

		while(r - l > 1){
			int m = l + (r - l) / 2;

			vector<int> vec = ask(m);

			if(vec[0] + vec[1] == maxcnt && (m + 1 - vec[0]) - prefix == m - pos + 1) l = m;
			else r = m;
		}

		prefix += (l - pos + 1);

		for(int i = pos; i <= l; i++) ismax[i] = true;

		pos = max(pos + 1, l + 1);
	}

	for(int i = 0; i < n; i++){
		if(!ismax[i]){
			vector<int> vec = ask(i);

			if(vec[0] + vec[1] == 0) return i;
		}
	}

	return -1;
}

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