This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #define LOCAL
#include "bits/stdc++.h"
#ifndef LOCAL
#include "icc.h"
#endif
using namespace std;
#ifdef LOCAL
int query(int size_a, int size_b, int a[], int b[]) {
cout << "set A: ";
for(int i = 0; i < size_a; i++) {
cout << a[i] << " ";
}
cout << endl;
cout << "set B: ";
for(int i = 0; i < size_b; i++) {
cout << b[i] << " ";
}
cout << endl;
int x;
cin >> x;
return x;
}
void setRoad(int a, int b) {
cout << "join " << a << " and " << b << endl;
}
#endif
int ask(vector <int> p, vector <int> q) {
int size_a = p.size();
int size_b = q.size();
if(size_a == 0 || size_b == 0) return 0;
int *a, *b;
a = new int [size_a];
b = new int [size_b];
for(int j = 0; j < size_a; j++) {
a[j] = p[j];
}
for(int j = 0; j < size_b; j++) {
b[j] = q[j];
}
return query(size_a, size_b, a, b);
}
int par[200];
vector <int> node[200];
int root(int x) {
if(par[x] == x) return par[x];
else return par[x] = root(par[x]);
}
void join(int x, int y) {
x = root(x);
y = root(y);
if(node[x].size() > node[y].size()) swap(x, y);
if(x != y) {
par[x] = y;
for(auto i : node[x]) {
node[y].push_back(i);
}
node[x].clear();
}
}
vector <int> component (vector <int> v) {
vector <int> ans;
for(auto i : v) {
for(auto j : node[i]) {
ans.push_back(j);
}
}
return ans;
}
int askComp(vector <int> p, vector <int> q) {
p = component(p);
q = component(q);
return ask(p, q);
}
int n;
vector <int> setA, setB;
int search(int b, int e) {
if(b == e) {
return setB[b];
}
int m = (b + e) >> 1;
vector <int> v;
for(int i = b; i <= m; i++) {
v.push_back(setB[i]);
}
if(askComp(setA, v)) return search(b, m);
else return search(m + 1, e);
}
int find(int b, int e) {
if(b == e) {
return setB[b];
}
int m = (b + e) >> 1;
vector <int> v;
for(int i = b; i <= m; i++) {
v.push_back(setB[i]);
}
if(ask(setA, v)) return find(b, m);
else return find(m+1, e);
}
void find_road() {
int xor_val = 0;
int comp = 0;
set <int> s;
for(int i = 1; i <= n; i++) {
if(s.find(root(i)) == s.end()) {
s.insert(root(i));
}
}
vector <int> ls (s.begin(), s.end());
comp = ls.size();
for(int i = 0; i < 7; i++) {
vector <int> p, q;
for(int j = 0; j < comp; j++) {
if((j >> i) & 1) q.push_back(ls[j]);
else p.push_back(ls[j]);
}
if(askComp(p, q)) {
setA = p;
setB = q;
xor_val |= 1 << i;
}
}
int comp1 = search(0, setB.size() - 1);
int idx = 0;
for(int i = 0; i < comp; i++) {
if(ls[i] == comp1) {
idx = i;
}
}
int comp2 = ls[idx ^ xor_val];
setA = node[comp1];
setB = node[comp2];
int node1 = find(0, setB.size() - 1);
setB.swap(setA);
int node2 = find(0, setB.size() - 1);
setRoad(node1, node2);
join(comp1, comp2);
}
void run(int N) {
n = N;
for(int i = 1; i <= n; i++) {
node[i].clear();
node[i].push_back(i);
par[i] = i;
}
for(int i = 1; i < n; i++) {
find_road();
}
}
#ifdef LOCAL
int main(int argc, char const *argv[])
{
run(6);
return 0;
}
#endif
# | 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... |