Submission #593847

#	Time	Username	Problem	Language	Result	Execution time	Memory
593847		AlperenT	The Big Prize (IOI17_prize)	C++17	99.09 / 100	64 ms	932 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 = 450, K = 1600, DIFF = 10000;

int maxcnt = 0;

map<int, vector<int>> mp;

vector<int> query(int pos){
	if(mp.find(pos) == mp.end()) mp[pos] = ask(pos);

	return mp[pos];
}

int find_best(int n){
	set<int> st;

	while(st.size() < n && st.size() < TRYMAX) st.insert(int_rand(0, n - 1));

	for(auto i : st){
		vector<int> vec = query(i);

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

	vector<bool> ismax(n, false);

	int pos = 0, prefix = 0;

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

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

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

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

			auto it = mp.lower_bound(m);

			int m2 = m;

			if(it != mp.end()){
				if(it->first > l && it->first < r && abs(it->first - m) <= DIFF) m2 = it->first;
			}

			if(it != mp.begin()){
				if(prev(it)->first > l && prev(it)->first < r && abs(prev(it)->first - m) <= DIFF) m2 = prev(it)->first;
			}

			m = m2;

			vector<int> vec = query(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 = query(i);

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

	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  while(st.size() < n && st.size() < TRYMAX) st.insert(int_rand(0, n - 1));
      |        ~~~~~~~~~~^~~

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