#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int p[101];
vector <int> ve[101],root;
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
i=f(i);
j=f(j);
if (i>j)
swap(i,j);
p[j]=i;
for (int k:ve[j])
ve[i].push_back(k);
ve[j].clear();
}
int ask(int x, int y, int a[], int b[]){
int A[x],B[y];
for (int i=0;i<x;i++)
A[i]=a[i];
for (int j=0;j<y;j++)
B[j]=b[j];
return query(x,y,A,B);
}
int n;
void findroad(){
root.clear();
for (int i=1;i<=n;i++)
if (f(i)==i)
root.push_back(i);
for (int i=0;(1<<i)<root.size();i++){
int sa=0,sb=0;
for (int j=0;j<root.size();j++)
if ((j>>i)&1)
sb+=ve[root[j]].size();
else
sa+=ve[root[j]].size();
int a[sa],b[sb],x=0,y=0;
for (int j=0;j<root.size();j++){
if ((j>>i)&1)
for (int u:ve[root[j]]){
b[y]=u;
y++;
}
else
for (int u:ve[root[j]]){
a[x]=u;
x++;
}
}
if (query(sa,sb,a,b)){
int l=1,r=sa,kq=-1,kq2=-1;
while (l<=r){
int mid=(l+r)>>1;
if (ask(mid,sb,a,b)){
kq=mid;
r=mid-1;
}
else
l=mid+1;
}
l=1,r=sb;
while (l<=r){
int mid=(l+r)>>1;
if (ask(sa,mid,a,b)){
kq2=mid;
r=mid-1;
}
else
l=mid+1;
}
setRoad(a[kq-1],b[kq2-1]);
unite(a[kq-1],b[kq2-1]);
break;
}
}
}
void Run(int N){
n=N;
for (int i=1;i<=n;i++){
p[i]=i;
ve[i].push_back(i);
}
for (int i=1;i<n;i++)
findroad();
}
int main(){
cin >> n;
Run(n);
}
Compilation message
icc.cpp: In function 'void findroad()':
icc.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i=0;(1<<i)<root.size();i++){
| ~~~~~~^~~~~~~~~~~~
icc.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int j=0;j<root.size();j++)
| ~^~~~~~~~~~~~
icc.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int j=0;j<root.size();j++){
| ~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccyYLE7I.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVHlvHF.o:icc.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccyYLE7I.o: in function `main':
grader.cpp:(.text.startup+0x17): undefined reference to `run'
collect2: error: ld returned 1 exit status
