#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;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
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';
}*/
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);
}
while(true){
sort(g.begin(),g.end());
shuffle(g.begin(),g.end(),rng);
int m = g.size();
int ptr = 0;
for(int k=0;k<m/2;k++){
for(int x:p[g[k]])A[ptr++] = x;
}
an = ptr;
bn = n-ptr;
ptr = 0;
for(int k=m/2;k<m;k++){
for(int x:p[g[k]])B[ptr++] = x;
}
if(query(an,bn,A,B))break;
}
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);
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
468 KB |
Ok! 103 queries used. |
2 |
Correct |
5 ms |
468 KB |
Ok! 96 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
468 KB |
Ok! 526 queries used. |
2 |
Correct |
56 ms |
484 KB |
Ok! 832 queries used. |
3 |
Correct |
47 ms |
488 KB |
Ok! 804 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
115 ms |
468 KB |
Ok! 1481 queries used. |
2 |
Correct |
160 ms |
492 KB |
Ok! 2110 queries used. |
3 |
Correct |
124 ms |
492 KB |
Ok! 1703 queries used. |
4 |
Correct |
125 ms |
468 KB |
Ok! 1678 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
133 ms |
492 KB |
Ok! 1638 queries used. |
2 |
Correct |
137 ms |
496 KB |
Ok! 1666 queries used. |
3 |
Correct |
138 ms |
488 KB |
Ok! 1828 queries used. |
4 |
Correct |
119 ms |
488 KB |
Ok! 1580 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
151 ms |
492 KB |
Too many queries! 1895 out of 1775 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
147 ms |
488 KB |
Too many queries! 1855 out of 1625 |
2 |
Halted |
0 ms |
0 KB |
- |