| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 604957 |
2022-07-25T11:11:24 Z |
CSQ31 |
ICC (CEOI16_icc) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int par[1000];
int find(int x){
if(x==par[x])return x;
return par[x] = find(par[x]);
}
void unite(int a,int b){
a = find(a);
b = find(b);
if(a==b)return;
par[a] = b;
}
int n;
int A[200],B[200],an,bn;
/*
int query(int a, int b, int *A, int *B){
int ans;
for(int i=0;i<a;i++)cout<<A[i]<<" ";
cout<<'\n';
for(int i=0;i<b;i++)cout<<B[i]<<" ";
cout<<'\n';
cin>>ans;
return ans;
}
void setRoad(int a, int b){
cout<<"added edge"<<'\n';
cout<<a<<" "<<b<<'\n';
}*/
typedef pair<int,int> pii;
#define fi first
#define se second
void run(int N){
n = N;
for(int i=1;i<=n;i++)par[i] = i;
for(int i=1;i<n;i++){
vector<int>g;
vector<vector<int>>p(n+1);
for(int j=1;j<=n;j++){
if(j==find(j))g.push_back(j);
p[find(j)].push_back(j);
}
vector<int>s1,s2;
int m = g.size();
vector<pii>range = {{0,m-1}};
while(true){
s1.clear();
s2.clear();
vector<pii>rn;
for(pii x:range){
int l = x.fi;
int r = x.se;
if(l==r)continue;
int mid = (l+r)/2;
rn.push_back({l,mid});
rn.push_back({mid+1,r});
for(int j=l;j<=mid;j++)s1.push_back(g[j]);
for(int j=mid+1;j<=r;j++)s2.push_back(g[j]);
}
int ptr = 0;
for(int x:s1){
for(int y:p[x])A[ptr++] = y;
}
an = ptr;
ptr = 0;
for(int x:s2){
for(int y:p[x])B[ptr++] = y;
}
bn = an+ptr
if(query(an,bn,A,B))break;
swap(range,rn);
}
int l = 1,r = an;
while(r>l){
int mid = (l+r)/2;
if(query(mid,bn,A,B))r = mid;
else l = mid+1;
}
int v = A[r-1];
l = 1;r = bn;
while(r>l){
int mid = (l+r)/2;
if(query(an,mid,A,B))r = mid;
else l = mid+1;
}
int u = B[r-1];
unite(v,u);
setRoad(v,u);
}
}
/*
int main()
{
int m;
cin>>m;
run(m);
}*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:71:15: error: expected ';' before 'if'
71 | bn = an+ptr
| ^
| ;
72 | if(query(an,bn,A,B))break;
| ~~
