#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
const int N = 100;
vector<int> A[N];
int col[N];
int n;
bool query_col(vector<int> a)
{
set<int> s(a.begin(), a.end());
vector<int> x, y;
Loop (i,0,n) {
if (s.count(col[i]))
x.push_back(i+1);
else
y.push_back(i+1);
}
if (x.empty() || y.empty())
return 0;
return query(x.size(), y.size(), &x[0], &y[0]);
}
bool query_range(vector<int> a, vector<int> b, int l, int r)
{
vector<int> v, u;
Loop (i,l,r)
v.push_back(a[i]+1);
Loop (i,0,b.size())
u.push_back(b[i]+1);
return query(v.size(), u.size(), &v[0], &u[0]);
}
vector<int> dfs(int v, int p, int c)
{
vector<int> ans = {v};
if (c >= 0)
col[v] = c;
for (int u : A[v]) {
if (u != p) {
auto tmp = dfs(u, v, c);
for (int x : tmp)
ans.push_back(x);
}
}
return ans;
}
int bin_search(vector<int> a, vector<int> b)
{
int l = 0, r = a.size()-1;
while (l < r) {
int mid = (l+r)/2;
if (query_range(a, b, l, mid+1))
r = mid;
else
l = mid+1;
}
return l;
}
vector<int> cv[N];
int cv_len;
void find_next()
{
cv_len = 0;
memset(col, -1, sizeof(col));
Loop (i,0,n) {
if (col[i] == -1) {
cv[cv_len] = dfs(i, -1, cv_len);
++cv_len;
}
}
int lg = __lg(cv_len-1)+1;
int delta = 0, first = 0;
Loop (i,0,lg) {
vector<int> v;
Loop (j,0,cv_len)
if (j & (1<<i))
v.push_back(j);
if (query_col(v))
delta ^= (1<<i);
}
int fbit = __builtin_ctz(delta);
first ^= 1 << fbit;
Loop (i,0,lg) {
if (i == fbit)
continue;
vector<int> v;
Loop (j,0,cv_len)
if ((j & (1<<i)) && (j & (1<<fbit)))
v.push_back(j);
if (query_col(v))
first ^= (1<<i);
}
int second = first ^ delta;
vector<int> a = cv[first], b = cv[second];
int v = a[bin_search(a, b)];
int u = b[bin_search(b, a)];
setRoad(v+1, u+1);
A[v].push_back(u);
A[u].push_back(v);
}
void run(int n)
{
::n = n;
Loop (i,0,n-1)
find_next();
}
#ifdef local
int query(int size_a, int size_b, int a[], int b[])
{
cout << "query\n";
Loop (i,0,size_a)
cout << a[i] << ' ';
cout << '\n';
Loop (i,0,size_b)
cout << b[i] << ' ';
cout << '\n';
int ans;
cin >> ans;
return ans;
}
void setRoad(int a, int b)
{
cout << "setRoad\n";
cout << a << ' ' << b << '\n';
cout << "continue? ";
char c;
cin >> c;
if (c != 'y')
exit(0);
}
int main()
{
int n;
cin >> n;
run(n);
}
#endif
Compilation message
/usr/bin/ld: /tmp/ccYv2XZs.o: in function `query_range(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)':
icc.cpp:(.text+0x590): undefined reference to `query(int, int, int*, int*)'
/usr/bin/ld: /tmp/ccYv2XZs.o: in function `query_col(std::vector<int, std::allocator<int> >)':
icc.cpp:(.text+0xa37): undefined reference to `query(int, int, int*, int*)'
/usr/bin/ld: /tmp/ccYv2XZs.o: in function `find_next()':
icc.cpp:(.text+0x14b3): undefined reference to `setRoad(int, int)'
/usr/bin/ld: /tmp/ccXQLzzs.o: in function `main':
grader.cpp:(.text.startup+0x17): undefined reference to `run'
collect2: error: ld returned 1 exit status
