| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 754925 | MilosMilutinovic | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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;
}