#include <bits/stdc++.h> // Tomasz Nowak
#include "icc.h"
using namespace std; // XIII LO Szczecin
using LL = long long; // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
out << '{';
for(auto it = x.begin(); it != x.end(); ++it)
out << *it << (it == prev(x.end()) ? "" : ", ");
return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
cerr << x << "; ";
dump(args...);
}
#ifdef DEBUG
struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ": " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates
int query(vector<int> a, vector<int> b) {
int ta[size(a)], tb[size(b)];
REP(i, size(a))
ta[i] = a[i];
REP(i, size(b))
tb[i] = b[i];
return query(size(a), size(b), ta, tb);
}
vector<int> collapse(vector<vector<int>> v) {
vector<int> ret;
for(auto &vec : v)
for(int x : vec)
ret.emplace_back(x);
return ret;
}
int query(vector<vector<int>> a, vector<vector<int>> b) {
return query(collapse(a), collapse(b));
}
template<class T>
pair<T, T> split_half(T a) {
T left, right;
REP(i, size(a))
if(i % 2)
right.emplace_back(a[i]);
else
left.emplace_back(a[i]);
return {left, right};
}
template<class T>
T find(T a, T b) {
while(size(a) != 1 or size(b) != 1) {
if(size(a) < size(b))
swap(a, b);
auto [left, right] = split_half(a);
if(query(left, b))
a = left;
else
b = right;
}
return {a[0], b[0]};
}
template<class T>
T find(T a) {
while(true) {
shuffle(a.begin(), a.end(), rng);
auto [left, right] = split_half(a);
if(query(left, right))
return find(left, right);
}
}
void run(int n) {
vector<int> lead(n);
iota(lead.begin(), lead.end(), 0);
function<int (int)> find_leader = [&](int v) {
if(v == lead[v])
return v;
return lead[v] = find_leader(lead[v]);
};
REP(edge, n - 1) {
vector<vector<int>> in_lead(n);
REP(v, n)
in_lead[find_leader(v)].emplace_back(v);
vector<vector<int>> components;
REP(v, n)
if(lead[v] == v)
components.emplace_back(in_lead[v]);
for(auto &v : components)
shuffle(v.begin(), v.end(), rng);
auto ret1 = find(components);
auto ret = find(ret1[0], ret1[1]);
int v = ret[0],
u = ret[1];
debug(v, u);
setRoad(v, u);
lead[find_leader(v)] = find_leader(u);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
}
Compilation message
/tmp/ccqBAJbG.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccFSNF0K.o:icc.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
