//#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int n, fa[N];
int gfa(int x) { return fa[x] == x ? x : fa[x] = gfa(fa[x]); }
//void setRoad(int x, int y) {
// printf("new Road %d %d\n", x, y);
//}
bool query(vector<int> x, vector<int> y) {
int sz_x = x.size();
int sz_y = y.size();
int qx[sz_x], qy[sz_y];
for (int i = 0; i < sz_x; i++)
qx[i] = x[i];
for (int i = 0; i < sz_y; i++)
qy[i] = y[i];
return query(sz_x, sz_y, qx, qy);
// printf("query\n");
// for (int i : x) printf("%d ", i); printf("\n");
// for (int i : y) printf("%d ", i); printf("\n");
// int f;
// scanf("%d", &f);
// return f;
}
void add(vector<int>& v, int comp) {
for (int i = 1; i <= n; i++)
if (gfa(i) == gfa(comp))
v.push_back(i);
}
pair<int, int> find_road(vector<int> a, vector<int> b) {
pair<int, int> res;
int low = 0, high = a.size() - 1, pos = 0;
while (low <= high) {
int mid = low + high >> 1;
vector<int> q_vec;
for (int i = 0; i <= mid; i++)
q_vec.push_back(a[i]);
if (query(q_vec, b))
pos = mid, high = mid - 1;
else
low = mid + 1;
}
res.first = a[pos];
low = 0, high = b.size() - 1;
while (low <= high) {
int mid = low + high >> 1;
vector<int> q_vec;
for (int i = 0; i <= mid; i++)
q_vec.push_back(b[i]);
if (query(q_vec, a))
pos = mid, high = mid - 1;
else
low = mid + 1;
}
res.second = b[pos];
return res;
}
void run(int n) {
::n = n;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int iter = 1; iter <= n - 1; iter++) {
vector<int> v;
for (int i = 1; i <= n; i++)
if (gfa(i) == i)
v.push_back(i);
int sz = (int) v.size(), lg = 0;
while ((1 << lg) < sz) lg++;
int xr = 0;
for (int b = 0; b < lg; b++) {
vector<int> l, r;
for (int i = 0; i < sz; i++) {
if (i >> b & 1) {
add(l, v[i]);
} else {
add(r, v[i]);
}
}
if (query(l, r))
xr ^= (1 << b);
}
int f = -1;
for (int b = 0; b < lg; b++)
if (xr >> b & 1)
f = b;
if (f == -1) while (true) {}
int a = 0, b = 0;
for (int i = 0; i < lg; i++) {
if (xr >> i & 1) {
if (i == f) {
a += (1 << i);
continue;
}
vector<int> l, r;
for (int j = 0; j < sz; j++) {
if (j >> f & 1) {
if (j >> i & 1) add(l, v[j]);
} else {
if (!(j >> i & 1)) add(r, v[j]);
}
}
if (query(l, r))
a += (1 << i);
else
b += (1 << i);
} else {
vector<int> l, r;
for (int j = 0; j < sz; j++) {
if (j >> i & 1) continue;
if (j >> f & 1)
add(l, v[j]);
else
add(r, v[j]);
}
if (!query(l, r))
a += (1 << i), b += (1 << i);
}
}
vector<int> l, r;
for (int i = 1; i <= n; i++) {
if (gfa(i) == v[a])
l.push_back(i);
if (gfa(i) == v[b])
r.push_back(i);
}
pair<int, int> p = find_road(l, r);
setRoad(p.first, p.second);
fa[gfa(p.first)] = gfa(p.second);
}
}
int main() {
scanf("%d", &n);
run(n);
return 0;
}
Compilation message
icc.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
icc.cpp:18:18: error: could not convert 'sz_x' from 'int' to 'std::vector<int>'
18 | return query(sz_x, sz_y, qx, qy);
| ^~~~
| |
| int
icc.cpp: In function 'std::pair<int, int> find_road(std::vector<int>, std::vector<int>)':
icc.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = low + high >> 1;
| ~~~~^~~~~~
icc.cpp:47:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = low + high >> 1;
| ~~~~^~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:127:9: error: 'setRoad' was not declared in this scope
127 | setRoad(p.first, p.second);
| ^~~~~~~
icc.cpp: In function 'int main()':
icc.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
