Submission #425715

#	Time	Username	Problem	Language	Result	Execution time	Memory
425715		NachoLibre	The Big Prize (IOI17_prize)	C++17	100 / 100	96 ms	11364 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "prize.h"
#else
int _n;
vint _x;
vint ask(int i) {
	vint dr(2);
	for(int j = 0; j < _n; ++j) {
		if(_x[j] < _x[i]) ++dr[j > i];
	}
	return dr;
}
#endif

mt19937_64 rnd(time(0));
int R(int l, int r) {
	return l + rnd() % (r - l + 1);
}

int c;
vvint cch;
set<int> s;
vint A(int i) {
	if(cch[i][0] == -1) {
		// if(++c > 10000) exit(1);
		cch[i] = ask(i);
		s.insert(i);
	}
	return cch[i];
}

int find_best(int n) {
	c = 0;
	s.clear();
	cch.clear();
	cch.resize(n, vint(2, -1));
	int cm = 0;
	for(int i = 0; i < 100; ++i) {
		int x = R(0, n - 1);
		cm = max(cm, A(x)[0] + A(x)[1]);
		// if(A(x)[0] + A(x)[1] == +0) return x;
	}
	for(int i = 0; i < n; ++i) {
		#ifdef wambule
		cout << i << endl;
		#endif
		while(s.size() && (*s.begin()) <= i) {
			s.erase(s.begin());
		}
		if(A(i)[0] + A(i)[1] == +0) return i;
		if(A(i)[0] + A(i)[1] == cm) {
			int l = i, r = n - 1;
			while(s.size()) {
				int x = *s.begin();
				if(A(x)[1] == A(i)[1]) {
					s.erase(s.begin());
					l = x;
				} else {
					r = x - 1;
					break;
				}
			}
			#ifdef wambule
			cout << l << " " << r << endl;
			#endif
			while(l < r) {
				int m = l + r + 1 >> 1;
				while(A(m)[0] + A(m)[1] < cm) {
					--m;
					r = m;
				}
				if(A(m)[1] == A(i)[1]) l = m;
				else r = m - 1;
				#ifdef wambule
				cout << l << " " << r << endl;
				#endif
			}
			i = l;
		}
	}
	return 0;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	_x = {3, 2, 3, 1, 3, 3, 2, 3};
	_n = _x.size();
	cout << find_best(_n) << " " << c << " []" << endl;
	_x = {3, 3, 3, 2, 2, 3, 3, 1};
	_n = _x.size();
	cout << find_best(_n) << " " << c << " []" << endl;
	return 0;
}
#endif

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:73:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~

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