Submission #761717

#	Time	Username	Problem	Language	Result	Execution time	Memory
761717		minhcool	The Big Prize (IOI17_prize)	C++17	90 / 100	59 ms	1872 KiB

prize

#ifndef local
#include "prize.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
#ifdef local
 
int n, arr[N];
 
vector<int> ask(int x){
	vector<int> v;
	int num = 0;
	for(int i = x - 1; i >= 0; i--) num += (arr[i] < arr[x]);
	v.pb(num);
	num = 0;
	for(int i = x + 1; i < n; i++) num += (arr[i] < arr[x]);
	v.pb(num);
	return v;
}
#endif 
 
ii gett[N];
 
ii cal(int x){
	if(gett[x].fi || gett[x].se) return gett[x];
	vector<int> v = ask(x);
	return gett[x] = {v[0], v[1]};
}
 
int find_best(int n){
	if(n <= 1000){
	//	exit(0);
		for(int i = 0; i < n; i++){
			ii temp = cal(i);
		//	cout << temp.fi << " " << temp.se << "\n";
			if(!(temp.fi + temp.se)) return i;
		}
		exit(0);
	}
	int maxi = -oo;
	for(int itr = 1; itr <= 500; itr++){
		int pos = rnd(0, n - 1);
		ii temp = cal(pos);
		maxi = max(maxi, temp.fi + temp.se);
	}
	int lst = -1, num = 0;
	while(1){
		int le = lst + 1, ri = n - 1;
		num++;
		int troll = 0;
		while(le < ri){
			int mid = (le + ri) >> 1;
			if(!troll){
				mid = min(mid, le + 500);
				troll = 1;
			}
			assert(le < n && ri < n && mid < n);
			ii temp = cal(mid);
            assert((temp.fi + temp.se) <= maxi);
			if((temp.fi + temp.se) != maxi) ri = mid;
			else if(temp.fi >= num) ri = mid;
			else le = mid + 1;
		}
		ii temp = cal(le);
        assert((temp.fi + temp.se) <= maxi);
		if(!(temp.fi + temp.se)) return le;
		lst = le;
	}
	assert(0);
}
 
/*
200000 5
1 2 5 26 199966
*/
 
//#define local
#ifdef local
void process(){
	int m;
	cin >> n >> m;
	int sum = 0;
	for(int i = 1; i <= m; i++){
		int x;
		cin >> x;
		for(int j = sum; j <= sum + x - 1; j++) arr[j] = i;
		sum += x;
	}
	reverse(arr, arr + n);
	//shuffle(arr + 1, arr + n + 1, default_random_engine(rnd(1, 7405)));
	cout << find_best(n) << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message (stderr)

prize.cpp:21:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

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