| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341040 |
2020-12-28T23:33:19 Z |
ogibogi2004 |
ICC (CEOI16_icc) |
C++14 |
|
1 ms |
492 KB |
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
const int MAXN=128;
vector<vector<int> >comp;
int ans1,ans2,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++)
{
a[j-l2]=comp[i2][j];
}
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)
{
int low=0,high=comp[idx1].size()-1,mid;
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;
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)
{
int low=0,high=v1.size()-1,ans11,ans22,mid;
vector<int>xd;
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;
}
low=0,high=v2.size()-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;
}
solve(ans11,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<k;i++)
{
v2.push_back(v[i]);
}
if(ask(v1,v2))
{
solve(v1,v2);
return;
}
v1.clear();v2.clear();
for(int i=0;i<k;i+=2)
{
v1.push_back(v[i]);
}
for(int i=1;i<k;i+=2)
{
v2.push_back(v[i]);
}
if(ask(v1,v2))
{
solve(v1,v2);
return;
}
v1.clear();v2.clear();
for(int i=0;i<k;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;
}
void run(int N)
{
n=N;
for(int i=1;i<=n;i++)
{
comp.push_back({i});
}
for(int i=1;i<n;i++)
{
vector<int>vv;
for(int j=0;j<comp.size();j++)
{
vv.push_back(j);
}
solve(vv);
setRoad(ans1,ans2);
add_edge(ans1,ans2);
}
}
Compilation message
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<comp.size();i++)
| ~^~~~~~~~~~~~
icc.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<comp.size();i++)
| ~^~~~~~~~~~~~
icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=0;i<v3.size();i++)a[i]=v3[i];
| ~^~~~~~~~~~
icc.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=0;i<v4.size();i++)b[i]=v4[i];
| ~^~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:170:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
170 | if(v.size()*2==k)k/=2;
| ~~~~~~~~~~^~~
icc.cpp: In function 'void run(int)':
icc.cpp:219:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for(int j=0;j<comp.size();j++)
| ~^~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:136:7: warning: 'ans22' may be used uninitialized in this function [-Wmaybe-uninitialized]
136 | solve(ans11,ans22);
| ~~~~~^~~~~~~~~~~~~
icc.cpp:136:7: warning: 'ans11' may be used uninitialized in this function [-Wmaybe-uninitialized]
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:50:16: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | if(i==idx1||i==idx2)continue;
| ~^~~~~~
icc.cpp:50:7: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
50 | if(i==idx1||i==idx2)continue;
| ~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
