This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> g[101];
int bt[101][100];
/*
int query(int n,int m,int* a,int* b){
cout<<n<<" "<<m<<endl;
for(int i = 0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
for(int i = 0;i<m;i++) cout<<b[i]<<" ";
cout<<endl;
int x;
cin>>x;
return x;
}*/
int a[101];
int b[101];
void run(int N){
int n = N;
for(int i = 1;i<=n;i++) g[i].push_back(i);
vector<int> v;
for(int i = 1;i<=n;i++) v.push_back(i);
int k = n-1;
while(k--){
for(int i = 0;i<v.size();i++){
for(int j = 0;j<20;j++){
bt[i][j] = (v[i]>>j)&1;
}
}
vector<int> f,s;
for(int i = 0;;i++){
f.clear();
s.clear();
for(int j = 0;j<v.size();j++){
if(bt[j][i]) f.push_back(v[j]);
else s.push_back(v[j]);
}
if(f.size() == 0 || s.size() == 0) continue;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int ps1 = 0;
int ps2 = 0;
for(int j = 0;j<f.size();j++){
// a[j] = f[j];
for(int jj = 0;jj<g[f[j]].size();jj++){
a[ps1++] = g[f[j]][jj];
}
}
for(int j = 0;j<s.size();j++){
// b[j] = s[j];
for(int jj = 0;jj<g[s[j]].size();jj++){
b[ps2++] = g[s[j]][jj];
}
}
int x;
x = query(ps1,ps2,a,b);
if(x) break;
}
int l = 0,r = f.size()-1;
int ans;
int ps1 = 0;
int ps2 = 0;
for(int j = 0;j<f.size();j++){
for(int jj = 0;jj<g[f[j]].size();jj++){
a[ps1++] = g[f[j]][jj];
}
}
for(int j = 0;j<s.size();j++){
for(int jj = 0;jj<g[s[j]].size();jj++){
b[ps2++] = g[s[j]][jj];
}
}
f.clear();
s.clear();
for(int j = 0;j<ps1;j++) f.push_back(a[j]);
for(int j = 0;j<ps2;j++) s.push_back(b[j]);
l = 0,r = f.size()-1;
// ans = 0;
for(int j = 0;j<s.size();j++) b[j] = s[j];
while(l<=r){
/*if(l == r){
break;
}*/
int mid = (l+r)/2;
memset(a,0,sizeof(a));
// memset(b,0,sizeof(b));
int ps = 0;
for(int j = l;j<=mid;j++){
a[ps] = f[j];
ps++;
}
int x;
x = query(mid-l+1,s.size(),a,b);
if(x){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
l = 0,r = s.size()-1;
// ans2;
int ans2;
memset(a,0,sizeof(a));
for(int j = 0;j<f.size();j++) a[j] = f[j];
while(l<=r){
/* if(l == r){
break;
}*/
int mid = (l+r)/2;
memset(b,0,sizeof(b));
int ps = 0;
for(int j = l;j<=mid;j++){
b[ps] = s[j];
ps++;
}
int x;
x = query(f.size(),mid-l+1,a,b);
if(x){
ans2 = mid;
r = mid-1;
}
else l = mid+1;
}
ans = f[ans];
ans2 = s[ans2];
setRoad(ans,ans2);
// cout<<"found "<<ans<<" "<<ans2<<endl;
int comp1,comp2;
for(int j = 1;j<=n;j++){
for(int jj = 0;jj<g[j].size();jj++){
if(g[j][jj] == ans){
comp1 = j;
break;
}
}
}
for(int j = 1;j<=n;j++){
for(int jj = 0;jj<g[j].size();jj++){
if(g[j][jj] == ans2){
comp2 = j;
break;
}
}
}
for(int j = 0;j<g[comp2].size();j++){
g[comp1].push_back(g[comp2][j]);
}
g[comp2].clear();
v.clear();
for(int j = 1;j<=n;j++){
if(g[j].size()) v.push_back(j);
}
}
}
/*
int main() {
ios_base::sync_with_stdio(false);
run(4);
return 0;
}*/
Compilation message (stderr)
icc.cpp: In function 'void run(int)':
icc.cpp:26:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<v.size();i++){
~^~~~~~~~~
icc.cpp:35:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<v.size();j++){
~^~~~~~~~~
icc.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++){
~^~~~~~~~~
icc.cpp:46:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[f[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:50:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++){
~^~~~~~~~~
icc.cpp:52:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[s[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++){
~^~~~~~~~~
icc.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[f[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++){
~^~~~~~~~~
icc.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[s[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++) b[j] = s[j];
~^~~~~~~~~
icc.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++) a[j] = f[j];
~^~~~~~~~~
icc.cpp:132:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[j].size();jj++){
~~^~~~~~~~~~~~
icc.cpp:140:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[j].size();jj++){
~~^~~~~~~~~~~~
icc.cpp:147:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<g[comp2].size();j++){
~^~~~~~~~~~~~~~~~
icc.cpp:130:19: warning: 'comp2' may be used uninitialized in this function [-Wmaybe-uninitialized]
int comp1,comp2;
^~~~~
icc.cpp:127:22: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans2 = s[ans2];
^
icc.cpp:126:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans = f[ans];
^
# | 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... |