Submission #689629

#	Time	Username	Problem	Language	Result	Execution time	Memory
689629		whqkrtk04	The Big Prize (IOI17_prize)	C++17	20 / 100	532 ms	1048576 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

pii query(int i) {
	static vector<pii> M = vector<pii>(202020, {-1, -1});
	if(M[i].fi < 0 && M[i].se < 0) {
		vector<int> res = ask(i);
		return M[i] = {res[0], res[1]};
	} else return M[i];
}

bool validate(int x, int s, int e, int ma, int &mi, pii &qmi, vector<pii> &R) {
	if(x >= e || x < s) return false;
	pii tmp = query(x);
	if(tmp.fi+tmp.se != ma) {
		R.push_back({x, tmp.fi+tmp.se});
		return false;
	} else {
		mi = x; qmi = tmp;
		return true;
	}
}

vector<pii> solve(int s, int e, int cnt, int lcnt, int rcnt, int ma) {
	//cout << s << " " << e << " " << cnt << " " << lcnt << " " << rcnt << " " << ma << "\n";
	if(cnt == 0) return vector<pii>();
	vector<pii> ret;
	int cl = s+e>>1, cr = s+e>>1;
	pii qmi; int mi;
	while(true) {
		if(validate(cr, s, e, ma, mi, qmi, ret)) break;
		else cr++;
  		if(validate(cl-1, s, e, ma, mi, qmi, ret)) break;
		else cl--;
		if(cl < s && cr >= e) return ret;
	}
	qmi.fi -= lcnt, qmi.se -= rcnt;
	if(cr == mi) qmi.fi -= cr-cl;
	else qmi.se -= cr-cl;
	//cout << mi << " " << cl << " " << cr << "  " << qmi << "\n";
	vector<pii> L = solve(s, cl, qmi.fi, lcnt, rcnt+cr-cl+qmi.se, ma);
	vector<pii> R = solve(cr, e, qmi.se, lcnt+cr-cl+qmi.fi, rcnt, ma);
	for(auto i : L) ret.push_back(i);
	for(auto i : R) ret.push_back(i);
	return ret;
}

int find_max(int n) {
	std::random_device r;
	std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
	std::mt19937 eng(seed);
	int ma = 0;
	vector<int> A;
	for(int i = 0; i < n; i++) A.push_back(i);
	std::shuffle(A.begin(), A.end(), eng);
	//cout << A;
	for(int i = 0; i < min(n, 400); i++) {
		pii tmp = query(A[i]);
		ma = max(ma, tmp.fi+tmp.se);
	}
	return ma;
}

int find_best(int n) {
	int ma = find_max(n);
	//cout << ma << "\n";
	vector<pii> ans = solve(0, n, ma, 0, 0, ma);
	for(auto i : ans) if(i.se == 0) return i.fi;
	exit(EXIT_FAILURE);
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<std::pair<int, int> > solve(int, int, int, int, int, int)':
prize.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int cl = s+e>>1, cr = s+e>>1;
      |           ~^~
prize.cpp:43:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int cl = s+e>>1, cr = s+e>>1;
      |                        ~^~

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