| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 395938 | usachevd0 | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i) {
cerr << a[i] << ' ';
}
cerr << endl;
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
for (auto& x : v) {
stream << x << ' ';
}
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
const int maxN = 200005;
#ifdef DEBUG
int a[maxN];
int cnt[maxN];
pii f[maxN];
vector<int> ask(int i) {
return {f[i].fi, f[i].se};
}
#endif
pii res[maxN];
int val[maxN];
set<int> vals;
pii Ask(int i) {
if (res[i].fi != -1) {
return res[i];
}
auto a = ask(i);
val[i] = a[0] + a[1];
vals.insert(val[i]);
return res[i] = {a[0], a[1]};
}
int find_best(int n) {
memset(res, 255, sizeof res);
memset(val, 255, sizeof val);
vals.clear();
#define ASK(i) Ask(i); if (!val[i]) return i
int i = 0;
while (i < n) {
ASK(i);
bool i_not_max = val[i] != *vals.rbegin();
int vl = i;
int vr = n;
while (vr - vl > 1 && !i_not_max) {
int vm = (vl + vr) >> 1;
ASK(vm);
if (val[vm] == val[i]) {
if (res[i].fi == res[vm].fi) {
vl = vm;
} else {
vr = vm;
}
} else if (val[vm] > val[i]) {
i_not_max = true;
break;
} else {
vr = vm;
}
}
if (i_not_max) {
++i;
continue;
}
ASK(vr);
i = vr + 1;
}
throw;
}
#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
mt19937 rng(228);
int n = 5;
int C = 3;
for (int itr = 1; ; ++itr) {
int M = -1e9;
int one_i = rng() % n;
a[one_i] = 1;
fill(cnt, cnt + C + 1, 0);
for (int i = 0; i < n; ++i) {
if (i != one_i) {
a[i] = rng() % (C - 1) + 2;
}
chkmax(M, a[i]);
++cnt[a[i]];
f[i].fi = accumulate(cnt, cnt + a[i], 0);
}
bool bad = false;
for (int k = 2; k <= M; ++k) {
if (cnt[k] <= cnt[k - 1] * (ll)cnt[k - 1]) {
bad = true;
break;
}
}
if (bad) continue;
fill(cnt, cnt + C + 1, 0);
for (int i = n - 1; i >= 0; --i) {
++cnt[a[i]];
f[i].se = accumulate(cnt, cnt + a[i], 0);
}
int i = find_best(n);
assert(0 <= i && i < n && a[i] == 1);
debug(itr);
}
/*int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
f[i].fi = accumulate(cnt, cnt + a[i], 0);
}
fill(cnt, cnt + n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
++cnt[a[i]];
f[i].se = accumulate(cnt, cnt + a[i], 0);
}
mdebug(f, n);
int i = find_best(n);
debug(i);
assert(0 <= i && i < n && a[i] == 1);*/
return 0;
}
#endif