| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 580674 |
2022-06-21T15:30:25 Z |
andrei_boaca |
ICC (CEOI16_icc) |
C++14 |
|
228 ms |
636 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
mt19937 rng(time(NULL));
int n;
vector<int> dsu[105];
int comp[105],a[105],b[105],asize,bsize,A[105],old[105];
int comps[105][105],vals[105];
void dsu_merge(int c1,int c2)
{
if(dsu[c1].size()<dsu[c2].size())
swap(c1,c2);
for(int i:dsu[c2])
{
comp[i]=c1;
dsu[c1].push_back(i);
}
dsu[c2].clear();
}
int adj[105][105];
/*int query(int asize,int bsize, int v[105],int w[105])
{
for(int i=0;i<asize;i++)
for(int j=0;j<bsize;j++)
if(adj[v[i]][w[j]])
return 1;
return 0;
}
void setRoad(int x,int y)
{
cout<<x<<' '<<y<<'\n';
adj[x][y]=adj[y][x]=1;
}*/
void run(int N)
{
n=N;
for(int i=1;i<=n;i++)
{
dsu[i].push_back(i);
comp[i]=i;
}
int p=0;
int nr=n;
for(int z=1;z<n;z++,nr--)
{
int cnt=0;
/*int h,e;
cin>>h>>e;
adj[h][e]=adj[e][h]=1;*/
for(int i=1;i<=n;i++)
if(dsu[i].size())
{
cnt++;
for(int j:dsu[i])
comp[j]=cnt;
dsu[cnt]=dsu[i];
if(i!=cnt)
dsu[i].clear();
}
for(int i=1;i<=cnt;i++)
vals[i]=i;
int mid=(cnt+1)/2;
bool rev=0;
while(true)
{
asize=0;
for(int i=1;i<=mid;i++)
for(int q:dsu[vals[i]])
a[asize++]=q;
bsize=0;
for(int i=mid+1;i<=cnt;i++)
for(int q:dsu[vals[i]])
b[bsize++]=q;
if(query(asize,bsize,a,b))
break;
if(cnt<=40)
{
shuffle(vals+1,vals+cnt+1,rng);
continue;
}
vector<int> cand;
for(int i=1;i<=cnt;i++)
{
old[i]=vals[i];
vals[i]=0;
}
int poz=cnt-40;
for(int j=cnt-39;j<=cnt;j++)
cand.push_back(old[j]);
for(int i=1;i<=cnt;i++)
{
shuffle(cand.begin(),cand.end(),rng);
vals[i]=cand.back();
cand.pop_back();
if(poz>0)
{
cand.push_back(old[poz]);
poz--;
}
}
}
int st=0;
int dr=asize-1;
int x=0;
while(st<=dr)
{
int mij=(st+dr)/2;
int sza=0;
for(int i=0;i<=mij;i++)
A[sza++]=a[i];
int ans=query(sza,bsize,A,b);
if(ans==1)
{
x=a[mij];
dr=mij-1;
}
else
st=mij+1;
}
st=0;
dr=bsize-1;
int y=0;
while(st<=dr)
{
int mij=(st+dr)/2;
int sza=0;
for(int i=0;i<=mij;i++)
A[sza++]=b[i];
int ans=query(sza,asize,A,a);
if(ans==1)
{
y=b[mij];
dr=mij-1;
}
else
st=mij+1;
}
dsu_merge(comp[x],comp[y]);
setRoad(x,y);
}
}
/*int main()
{
int N;
cin>>N;
run(N);
}*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:63:14: warning: unused variable 'rev' [-Wunused-variable]
63 | bool rev=0;
| ^~~
icc.cpp:42:9: warning: unused variable 'p' [-Wunused-variable]
42 | int p=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Ok! 107 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 107 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
500 KB |
Ok! 546 queries used. |
| 2 |
Correct |
50 ms |
492 KB |
Ok! 837 queries used. |
| 3 |
Correct |
51 ms |
488 KB |
Ok! 809 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
492 KB |
Ok! 1597 queries used. |
| 2 |
Correct |
228 ms |
500 KB |
Ok! 2215 queries used. |
| 3 |
Correct |
154 ms |
636 KB |
Ok! 1731 queries used. |
| 4 |
Correct |
192 ms |
508 KB |
Ok! 1790 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
488 KB |
Ok! 1656 queries used. |
| 2 |
Correct |
162 ms |
588 KB |
Ok! 1675 queries used. |
| 3 |
Correct |
195 ms |
468 KB |
Ok! 1984 queries used. |
| 4 |
Correct |
147 ms |
620 KB |
Ok! 1638 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
197 ms |
504 KB |
Too many queries! 1960 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
504 KB |
Too many queries! 2025 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
