Submission #425272

#	Time	Username	Problem	Language	Result	Execution time	Memory
425272		NachoLibre	The Big Prize (IOI17_prize)	C++17	0 / 100	18 ms	11240 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);
}

vvint cch;
vint A(int i) {
	if(cch[i][0] == -1) cch[i] = ask(i);
	return cch[i];
}

int find_best(int n) {
	cch.resize(n, vint(2, -1));
	int cm = 0;
	for(int i = 1; i <= 30; ++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) {
		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(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;
			}
			i = l + 1;
		}
	}
	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) << endl;
	return 0;
}
#endif

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