#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef __ICC_H__
int query(int a, int b, int *A, int *B) {
printf("\nProgram queried:\n");
printf(" A:");
for (int i = 0; i < a; i++) printf(" %d", A[i]);
printf("\n");
printf(" B:");
for (int i = 0; i < b; i++) printf(" %d", B[i]);
printf("\n");
printf("\nAre those two groups connected? ");
int ans;
scanf("%d", &ans);
return ans;
}
#endif
void setRoad(int a, int b) {
printf("\n!!! Program set road between %d and %d.\n", a, b);
}
const int MAXN = 101;
int n;
int component_number;
int uf[MAXN];
int get(int a) { return uf[a] == a ? a : uf[a] = get(uf[a]); }
void join(int a, int b) { uf[get(b)] = get(a); }
void split(vector<int> &source, vector<int> &l, vector<int> &r) {
l.clear();
r.clear();
int mid = (int(source.size()) - 1) >> 1;
for (int i = 0; i < source.size(); i++) {
if (i <= mid) l.push_back(source[i]);
else r.push_back(source[i]);
}
}
void run(int _n) {
srand(129312);
n = _n;
component_number = _n;
for (int i = 1; i <= n; i++) uf[i] = i;
while (component_number > 1) {
vector<vector<int>> groups(1), new_groups;
vector<int> a, b;
bool component_direction[n+1];
for (int i = 1; i <= n; i++) if (uf[i] == i) groups[0].push_back(i);
while (true) {
a.clear(); b.clear();
new_groups.clear();
for (vector<int> &v : groups) {
int mid = (int(v.size()) - 1) >> 1;
vector<int> new_l, new_r;
for (int i = 0; i < v.size(); i++) {
if (i <= mid) {
component_direction[v[i]] = 0;
new_l.push_back(v[i]);
} else {
component_direction[v[i]] = 1;
new_r.push_back(v[i]);
}
}
new_groups.push_back(new_l);
new_groups.push_back(new_r);
}
for (int i = 1; i <= n; i++) {
if (component_direction[get(i)] == 0) a.push_back(i);
else b.push_back(i);
}
if (query(a.size(), b.size(), a.data(), b.data())) break;
swap(groups, new_groups);
}
vector<int> a_l, a_r, b_l, b_r;
while (a.size() > 1 && b.size() > 1) {
if (a.size() > 1) {
split(a, a_l, a_r);
if (query(a_l.size(), b.size(), a_l.data(), b.data())) swap(a, a_l);
else swap(a, a_r);
}
if (b.size() > 1) {
split(b, b_l, b_r);
if (query(a.size(), b_l.size(), a.data(), b_l.data())) swap(b, b_l);
else swap(b, b_r);
}
}
setRoad(a[0], b[0]);
join(a[0], b[0]);
component_number--;
}
}
int main() {
int n;
printf("n? ");
scanf("%d", &n);
run(n);
}
Compilation message
icc.cpp: In function 'void split(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
icc.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < source.size(); i++) {
~~^~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:68:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
icc.cpp: In function 'int main()':
icc.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
/tmp/ccPhyzs4.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXdTNha.o:icc.cpp:(.text.startup+0x0): first defined here
/tmp/ccPhyzs4.o: In function `setRoad':
grader.cpp:(.text+0x1ce0): multiple definition of `setRoad'
/tmp/ccXdTNha.o:icc.cpp:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status
