| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 494872 | flappybird | Minerals (JOI19_minerals) | 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 "minerals.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
#define ln '\n'
#define MAX 101010
#define C 0.618
ll rnd[MAX];
vector<ll> A, B; //A is old
ll chk[MAX];
ll ans[MAX];
ll rem[MAX];
ll num[MAX];
ll pass[MAX];
ll pv = 0;
ll pvv = 0;
ll query(ll x) {
rem[x] = !rem[x];
pv = pvv;
pvv = Query(rnd[x]);
return pvv;
}
void answer(ll x, ll y) {
Answer(rnd[x], rnd[y]);
}
void dnc(vector<ll> v1, vector<ll> v2, bool c = false) {
ll N = v1.size();
if (N == 1) {
ans[v1[0]] = v2[0];
return;
}
if (N == 2) {
if (!rem[B[v2[0]]] || !rem[B[v2[0]]]) query(B[v2[0]]);
if (rem[B[v2[0]]]) {
if (rem[B[v2[1]]]) query(B[v2[1]]);
ans[v1[0]] = v2[0];
ans[v1[1]] = v2[1];
if (query(A[v1[0]]) != pv) swap(ans[v1[0]], ans[v1[1]]);
}
else {
ans[v1[0]] = v2[1];
ans[v1[1]] = v2[0];
if (query(A[v1[0]]) != pv) swap(ans[v1[0]], ans[v1[1]]);
}
return;
}
ll i;
vector<ll> in, out;
for (i = 0; i < N; i++) (rem[B[v2[i]]] ? in : out).push_back(v2[i]);
ll sz = N * C;
if (abs(sz - in.size()) > abs(N * (1. - C) - in.size())) sz = N * (1. - C);
while (in.size() < sz) {
ll a = out.back();
out.pop_back();
query(B[a]);
in.push_back(a);
}
while (in.size() > sz) {
ll a = in.back();
in.pop_back();
query(B[a]);
out.push_back(a);
}
vector<ll> in1, out1;
for (i = 0; i < N; i++) {
if (c && pass[i]) in1.push_back(v1[i]);
else {
if (pv == query(A[v1[i]])) in1.push_back(v1[i]);
else out1.push_back(v1[i]);
}
}
dnc(in1, in);
dnc(out1, out);
}
void rnd_gen(ll N) {
//mt19937 engine((unsigned int)time(NULL));
//uniform_int_distribution<int> distribution(0, 1000000000);
//auto generator = bind(distribution, engine);
ll i;
ll j;
for (i = 1; i <= 2 * N; i++) rnd[i] = i;
for (j = 0; j < 2; j++) {
for (i = 2 * N; i > 1; i--) {
ll a = rand() % i + 1;
swap(rnd[i], rnd[a]);
}
}
}
ll anschk[MAX];
ll checked[MAX];
void Solve(int N) {
mt19937 engine((unsigned int)time(NULL));
uniform_int_distribution<int> distribution(0, 1000000000);
auto generator = bind(distribution, engine);
ll i;
rnd_gen(N);
for (i = 1; i <= 2 * N; i++) {
ll res = query(i);
if (res != pv) {
B.push_back(i);
chk[i] = 1;
}
else {
A.push_back(i);
num[A.size() - 1] = B.size();
chk[i] = 0;
}
}
for (i = 0; i < N; i++) if (num[i] <= N * C) pass[i] = 1;
vector<ll> v;
for (i = 0; i < N; i++) v.push_back(i);
dnc(v, v, 1);
for (i = 0; i < N; i++) answer(A[i], B[ans[i]]);
}