| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341058 |
2020-12-29T00:33:06 Z |
ogibogi2004 |
ICC (CEOI16_icc) |
C++14 |
|
202 ms |
748 KB |
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
const int MAXN=128;
vector<vector<int> >comp;
int ans1=-1,ans2=-1,n;
bool ask(int i1,int i2)
{
int size_a=comp[i1].size(),size_b=comp[i2].size();
int a[size_a];
int b[size_b];
for(int i=0;i<size_a;i++)a[i]=comp[i1][i];
for(int i=0;i<size_b;i++)b[i]=comp[i2][i];
return query(size_a,size_b,a,b);
}
bool ask(int i1,int l1,int r1,int i2,int l2,int r2)
{
int size_a=r1-l1+1;
int size_b=r2-l2+1;
int a[size_a],b[size_b];
for(int j=l1;j<=r1;j++)
{
a[j-l1]=comp[i1][j];
}
for(int j=l2;j<=r2;j++)
{
b[j-l2]=comp[i2][j];
}
//cout<<"ask for:\n";
//cout<<i1<<" "<<l1<<" "<<r1<<" "<<i2<<" "<<l2<<" "<<r2<<endl;
//cout<<"A: ";
//for(int i=0;i<size_a;i++)cout<<a[i]<<" ";
//cout<<endl;
//cout<<"B: ";
//for(int i=0;i<size_b;i++)cout<<b[i]<<" ";
//cout<<endl;
return query(size_a,size_b,a,b);
}
void add_edge(int u,int v)
{
int idx1,idx2;
for(int i=0;i<comp.size();i++)
{
for(auto xd:comp[i])
{
if(xd==u)idx1=i;
if(xd==v)idx2=i;
}
}
vector<vector<int> >newcomp;
newcomp.push_back(comp[idx1]);
for(auto xd:comp[idx2])
{
newcomp.back().push_back(xd);
}
for(int i=0;i<comp.size();i++)
{
if(i==idx1||i==idx2)continue;
newcomp.push_back(comp[i]);
}
comp=newcomp;
}
bool ask(vector<int>v1,vector<int>v2)
{
vector<int>v3,v4;
for(auto xd:v1)
{
for(auto dx:comp[xd])v3.push_back(dx);
}
for(auto xd:v2)
{
for(auto dx:comp[xd])v4.push_back(dx);
}
int size_a=v3.size();
int size_b=v4.size();
int a[size_a],b[size_b];
for(int i=0;i<v3.size();i++)a[i]=v3[i];
for(int i=0;i<v4.size();i++)b[i]=v4[i];
return query(size_a,size_b,a,b);
}
void solve(int idx1,int idx2)
{
//cout<<"solve89 "<<idx1<<" "<<idx2<<endl;
int low=0,high=comp[idx1].size()-1,mid;ans1=high+1;
while(low<=high)
{
mid=(low+high)/2;
if(ask(idx1,0,mid,idx2,0,comp[idx2].size()-1))
{
ans1=mid;
high=mid-1;
}
else low=mid+1;
}
ans1=comp[idx1][ans1];
low=0,high=comp[idx2].size()-1;ans2=high+1;
while(low<=high)
{
mid=(low+high)/2;
if(ask(idx2,0,mid,idx1,0,comp[idx1].size()-1))
{
ans2=mid;
high=mid-1;
}
else low=mid+1;
}
ans2=comp[idx2][ans2];
return;
}
void solve(vector<int>v1,vector<int>v2)
{
//cout<<"solve for:\n";
//for(auto xd:v1)cout<<xd<<" ";
//cout<<endl;
//for(auto xd:v2)cout<<xd<<" ";
//cout<<endl;
int low=0,high=v1.size()-1,ans11=high+1,ans22,mid;
vector<int>xd;
//cout<<"?1\n";
while(low<=high)
{
mid=(low+high)/2;
xd.clear();
for(int i=0;i<=mid;++i)
{
xd.push_back(v1[i]);
}
if(ask(xd,v2))
{
ans11=mid;
high=mid-1;
}
else low=mid+1;
}
//cout<<"?2\n";
low=0,high=v2.size()-1;ans2=high+1;
while(low<=high)
{
mid=(low+high)/2;
xd.clear();
for(int i=0;i<=mid;i++)
{
xd.push_back(v2[i]);
}
if(ask(xd,v1))
{
ans22=mid;
high=mid-1;
}
else low=mid+1;
}
//cout<<"?3\n";
//cout<<ans11<<" "<<ans22<<endl;
solve(v1[ans11],v2[ans22]);
}
void solve(vector<int>v)
{
if(v.size()==2)
{
solve({v[0]},{v[1]});
}
if(v.size()==3)
{
if(ask({v[0]},{v[1],v[2]}))
{
solve({v[0]},{v[1],v[2]});
return;
}
else solve({v[0],v[1]},{v[2]});
return;
}
if(v.size()==4)
{
if(ask({v[0],v[1]},{v[2],v[3]}))
{
solve({v[0],v[1]},{v[2],v[3]});
return;
}
else solve({v[0],v[2]},{v[1],v[3]});
}
vector<int>v1,v2;
int m=v.size(),k=1;
while(m)
{
k*=2;
m/=2;
}
if(v.size()*2==k)k/=2;
/*for(int i=0;i<k/2;i++)
{
v1.push_back(v[i]);
}
for(int i=k/2;i<v.size();i++)
{
v2.push_back(v[i]);
}
cout<<"v1:";
for(auto ico:v1)cout<<" "<<ico;
cout<<endl;
cout<<"v2:";
for(auto ico:v2)cout<<" "<<ico;
cout<<endl;
if(ask(v1,v2))
{
solve(v1,v2);
return;
}
v1.clear();v2.clear();
for(int i=0;i<v.size();i+=2)
{
v1.push_back(v[i]);
}
for(int i=1;i<v.size();i+=2)
{
v2.push_back(v[i]);
}
cout<<"v1:";
for(auto ico:v1)cout<<" "<<ico;
cout<<endl;
cout<<"v2:";
for(auto ico:v2)cout<<" "<<ico;
cout<<endl;
if(ask(v1,v2))
{
solve(v1,v2);
return;
}
v1.clear();v2.clear();
for(int i=0;i<v.size();i++)
{
if(i%2==0&&i>=k/2)v1.push_back(v[i]);
if(i%2==1&&i>=k/2)v2.push_back(v[i]);
if(i%2==1&&i<k/2)v1.push_back(v[i]);
if(i%2==0&&i<k/2)v2.push_back(v[i]);
}
solve(v1,v2);
return;*/
for(int i=1;i<=k/2;i*=2)
{
v1.clear();v2.clear();
for(int j=0;j<v.size();j++)
{
if(j&i)v1.push_back(v[j]);
else v2.push_back(v[j]);
}
if(i==k/2||ask(v1,v2))
{
solve(v1,v2);
return;
}
}
}
void run(int N)
{
n=N;
for(int i=1;i<=n;++i)
{
comp.push_back({i});
}
for(int i=1;i<n;++i)
{
ans1=-1;ans2=-1;
vector<int>vv;
for(int j=0;j<comp.size();++j)
{
vv.push_back(j);
}
solve(vv);
if(ans1==-1&&ans2==-1)
{
assert(false);
}
//cout<<"found "<<ans1<<" "<<ans2<<endl;
setRoad(ans1,ans2);
add_edge(ans1,ans2);
for(int j=0;j<comp.size();j++)
{
/*cout<<j<<":";
for(auto xd:comp[j])cout<<" "<<xd;
cout<<endl;*/
}
//cout<<"lol\n";
}
}
Compilation message
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0;i<comp.size();i++)
| ~^~~~~~~~~~~~
icc.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<comp.size();i++)
| ~^~~~~~~~~~~~
icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<v3.size();i++)a[i]=v3[i];
| ~^~~~~~~~~~
icc.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<v4.size();i++)b[i]=v4[i];
| ~^~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:188:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
188 | if(v.size()*2==k)k/=2;
| ~~~~~~~~~~^~~
icc.cpp:241:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
241 | for(int j=0;j<v.size();j++)
| ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:264:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
264 | for(int j=0;j<comp.size();++j)
| ~^~~~~~~~~~~~
icc.cpp:276:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
276 | for(int j=0;j<comp.size();j++)
| ~^~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:154:26: warning: 'ans22' may be used uninitialized in this function [-Wmaybe-uninitialized]
154 | solve(v1[ans11],v2[ans22]);
| ^
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:58:16: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
58 | if(i==idx1||i==idx2)continue;
| ~^~~~~~
icc.cpp:58:7: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
58 | if(i==idx1||i==idx2)continue;
| ~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
492 KB |
Ok! 141 queries used. |
| 2 |
Correct |
12 ms |
492 KB |
Ok! 140 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
492 KB |
Ok! 707 queries used. |
| 2 |
Correct |
52 ms |
492 KB |
Ok! 738 queries used. |
| 3 |
Correct |
52 ms |
492 KB |
Ok! 738 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
492 KB |
Ok! 1895 queries used. |
| 2 |
Correct |
168 ms |
492 KB |
Ok! 1742 queries used. |
| 3 |
Correct |
168 ms |
492 KB |
Ok! 1972 queries used. |
| 4 |
Correct |
169 ms |
492 KB |
Ok! 1894 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
492 KB |
Ok! 1952 queries used. |
| 2 |
Correct |
169 ms |
492 KB |
Ok! 1967 queries used. |
| 3 |
Correct |
170 ms |
492 KB |
Ok! 1777 queries used. |
| 4 |
Correct |
164 ms |
492 KB |
Ok! 1863 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
492 KB |
Ok! 1751 queries used. |
| 2 |
Correct |
170 ms |
492 KB |
Ok! 1770 queries used. |
| 3 |
Correct |
181 ms |
748 KB |
Ok! 1770 queries used. |
| 4 |
Incorrect |
169 ms |
492 KB |
Too many queries! 1798 out of 1775 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
716 KB |
Too many queries! 1764 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
