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>
#include "icc.h"
using namespace std;
void run(int n) {
vector<vector<int>> comps(n);
vector<int> rep(n);
for (int i = 0; i < n; ++i) {
comps[i].push_back(i);
rep[i] = i;
}
auto comp_query = [&](vector<int> &as, vector<int> &bs) {
static int a[100], b[100];
int cnta = 0;
for (int u: as)
for (int e: comps[u])
a[cnta++] = e + 1;
int cntb = 0;
for (int u: bs)
for (int e: comps[u])
b[cntb++] = e + 1;
return query(cnta, cntb, a, b);
};
auto vec_query = [&](vector<int> &as, vector<int> &bs) {
static int a[100], b[100];
int cnta = 0;
for (int u: as)
a[cnta++] = u + 1;
int cntb = 0;
for (int u: bs)
b[cntb++] = u + 1;
return query(cnta, cntb, a, b);
};
auto turn = [&](int x) {
static mt19937 rng(time(0));
vector<int> xs, ys;
while (true) {
vector<int> as, bs;
for (int i = 0; i < x; ++i)
if (rng()%2) as.push_back(i);
else bs.push_back(i);
if (comp_query(as, bs)) {
for (int l: as)
for (int u: comps[l])
xs.push_back(u);
for (int r: bs)
for (int u: comps[r])
ys.push_back(u);
break;
}
}
// cerr << "SETS:\n";
// for (int x: xs)
// cerr << x << " ";
// cerr << "\n";
// for (int y: ys)
// cerr << y << " ";
// cerr << "\n";
int l = 0, r = xs.size();
while (l < r - 1) {
int m = (l + r)/2;
vector<int> qs;
for (int i = l; i < m; ++i)
qs.push_back(xs[i]);
if (vec_query(qs, ys)) r = m;
else l = m;
}
int u = xs[l];
l = 0, r = ys.size();
while (l < r - 1) {
int m = (l + r)/2;
vector<int> qs;
for (int i = l; i < m; ++i)
qs.push_back(ys[i]);
if (vec_query(qs, xs)) r = m;
else l = m;
}
int v = ys[l];
return make_pair(u, v);
};
auto swap_comps = [&](int a, int b) {
swap(comps[a], comps[b]);
for (int u: comps[a]) rep[u] = a;
for (int v: comps[b]) rep[v] = b;
};
for (int i = n; i > 1; --i) {
auto [u, v] = turn(i);
swap_comps(rep[u], i - 1);
swap_comps(rep[v], i - 2);
for (int u: comps[i-1]) {
comps[i-2].push_back(u);
rep[u] = i-2;
}
setRoad(u + 1, v + 1);
cerr << "REP: ";
for (int r: rep)
cerr << r << " ";
cerr << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |