Submission #475932

#	Time	Username	Problem	Language	Result	Execution time	Memory
475932		hhhhaura	The Big Prize (IOI17_prize)	C++14	20 / 100	135 ms	2492 KiB

prize

#include "prize.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define big 4172398721
#define MOD 1000000007
using namespace std;
#define pii pair<int, int>
#ifdef wiwihorz
#define print(a...) cerr << "Line: " << __LINE__, kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
int x;
random;
map<int, pii> mp;
pii Ask(int x) {
	if(mp.find(x) == mp.end()) {
		vector<int> v;
		v = ask(x);
		mp[x] = {v[0], v[1]};
	}
	return mp[x];
}
int solve(int L, int R, int tot, int pre) {
//	print(L, R, tot, pre);
	if(L == R) {
		pii p = Ask(L);
		return (p.first + p.second ? -1 : L);
	}
	int mid = (L + R) / 2, piv = -1, ans = -1;
	rep(i, mid + 1, R) {
		pii p = Ask(i);
		if(p.first + p.second == x) {
			piv = i;
			break;
		}
		else ans = max(ans, solve(i, i, 1, 0));
	}
	if(piv < 0) ans = (tot - (R - mid) ? max(ans, solve(L, mid, tot - (R - mid), pre)) : ans);
	else {
		pii p = Ask(piv);
		int left = p.first - pre - (piv - mid - 1);
		int right = tot - p.first + pre;
		if(left) ans = max(ans, solve(L, mid, left, pre));
		if(right) ans = max(ans, solve(piv, R, right, p.first)); 
	}
	return ans;
}
int find_best(int n) {
	x = 0;
	vector<pii> s;
	rrep(i, 0, n - 1) s.push_back({big * rnd() % MOD, i});
	sort(all(s));
	rep(i, 0, min(249, n) - 1) {
		pii p = Ask(s[i].second);
		x = max(x, p.first + p.second);
	}
	return solve(0, n - 1, x, 0);
}

Compilation message (stderr)

prize.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
prize.cpp:17:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
      |             ^~~~
prize.cpp:17:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L, auto R) { while(L < R)cerr << *L << " \n"[next(L) == R], ++L; }
      |                     ^~~~

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