| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713477 |
2023-03-22T08:52:44 Z |
lam |
ICC (CEOI16_icc) |
C++14 |
|
142 ms |
592 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 110;
vector<vector<int>> chan[maxn],le[maxn];
vector <int> comp[maxn];
int n,m;
int p[maxn],s[maxn];
//bool query(int x, int y, int a[], int b[])
//{
// cout<<"query"<<endl;
// for (int i=0; i<x; i++) cout<<a[i]<<' '; cout<<endl;
// for (int i=0; i<y; i++) cout<<b[i]<<' '; cout<<endl;
// bool has; cin>>has; return has;
//}
//void setRoad(int u, int v)
//{
// cout<<"SetRoad "<<u<<' '<<v<<endl;
//}
int get(int x)
{
return p[x]=(p[x]==x)?x:get(p[x]);
}
void hop(int x, int y)
{
x=get(x); y=get(y); if (x==y) return;
if (s[x]>s[y]) swap(x,y);
s[y]+=s[x];
p[x]=y;
for (int i:comp[x]) comp[y].push_back(i);
}
bool query2(int sz1, int sz2, vector <int> tmp1, vector <int> tmp2)
{
int a[110], b[110];
int x=0,y=0;
for (int i=0; i<sz1; i++) for (int j:comp[tmp1[i]]) a[x++] = j;
for (int i=0; i<sz2; i++) for (int j:comp[tmp2[i]]) b[y++] = j;
return query(x,y,a,b);
}
bool query3(int sz1, int sz2, vector <int> tmp1, vector <int> tmp2)
{
int a[110], b[110];
int x=0,y=0;
for (int i=0; i<sz1; i++) a[i] = tmp1[i];
for (int i=0; i<sz2; i++) b[i] = tmp2[i];
return query(sz1,sz2,a,b);
}
void dnc(int lx, int rx, vector <int> tmp, int level)
{
if (lx==rx) return;
random_shuffle(tmp.begin(),tmp.end());
int mid=(lx+rx)/2;
vector <int> tmp_chan, tmp_le;
for (int i=lx; i<=rx; i++) if (i<=mid) tmp_le.push_back(tmp[i-lx]);
else tmp_chan.push_back(tmp[i-lx]);
le[level].push_back(tmp_le); chan[level].push_back(tmp_chan);
dnc(lx,mid,tmp_le,level+1);
dnc(mid+1,rx,tmp_chan,level+1);
}
ii trace(vector <int> tmp_le, vector <int> tmp_chan)
{
if (tmp_chan.size() > tmp_le.size()) swap(tmp_le, tmp_chan);
if (tmp_le.size()==tmp_chan.size()&&tmp_le.size()==1)
{
return {tmp_le[0], tmp_chan[0]};
}
int mid = (tmp_le.size() - 1)/2;
random_shuffle(tmp_le.begin(),tmp_le.end());
vector <int> tmp_le1, tmp_le2;
for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
else tmp_le2.push_back(tmp_le[i]);
bool has = query2(tmp_le1.size(),tmp_chan.size(),tmp_le1,tmp_chan);
if (has) return trace(tmp_le1,tmp_chan);
else return trace(tmp_le2,tmp_chan);
}
ii trace2(vector <int> tmp_le, vector <int> tmp_chan)
{
if (tmp_chan.size() > tmp_le.size()) swap(tmp_le, tmp_chan);
if (tmp_le.size()==tmp_chan.size()&&tmp_le.size()==1)
{
return {tmp_le[0], tmp_chan[0]};
}
int mid = (tmp_le.size() - 1)/2;
random_shuffle(tmp_le.begin(),tmp_le.end());
vector <int> tmp_le1, tmp_le2;
for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
else tmp_le2.push_back(tmp_le[i]);
bool has = query3(tmp_le1.size(),tmp_chan.size(),tmp_le1,tmp_chan);
if (has) return trace2(tmp_le1,tmp_chan);
else return trace2(tmp_le2,tmp_chan);
}
void run(int N)
{
n=N;
for (int i=1; i<=n; i++) p[i]=i, s[i]=1, comp[i].clear(), comp[i].push_back(i);
for (int it=1; it<=n-1; it++)
{
vector <int> tmp;
for (int i=1; i<=n; i++)
{
if (p[i]==i) tmp.push_back(i); chan[i].clear(), le[i].clear();
}
m=tmp.size();
// for (int i=1; i<=n; i++) cerr<<le[i].size()<<','<<chan[i].size()<<' '; cerr<<endl;
dnc(1,m,tmp,1);
int level = 1;
while (true)
{
vector <int> tmp_le, tmp_chan;
for (vector <int> i:le[level]) for (int j:i) tmp_le.push_back(j);
for (vector <int> i:chan[level]) for (int j:i) tmp_chan.push_back(j);
bool has = query2(tmp_le.size(),tmp_chan.size(),tmp_le,tmp_chan);
if (has==1) break;
level++;
}
int l=0; int r=le[level].size()-1;
int ans=-1;
if (l==r) ans = l;
else
while (l<=r)
{
int mid=(l+r)/2;
vector <int> tmp_le, tmp_chan;
for (int i=mid; i<le[level].size(); i++)
for (int j:le[level][i]) tmp_le.push_back(j);
for (int i=mid; i<chan[level].size(); i++)
for (int j:chan[level][i]) tmp_chan.push_back(j);
bool has = query2(tmp_le.size(),tmp_chan.size(),tmp_le,tmp_chan);
if (has)
{
ans = mid;
l=mid+1;
}
else r=mid-1;
}
ii canh = trace(le[level][ans],chan[level][ans]);
canh = trace2(comp[canh.ff],comp[canh.ss]);
setRoad(canh.ff, canh.ss);
hop(canh.ff,canh.ss);
}
return;
}
//signed main()
//{
// int temp; cin>>temp;
// run(temp);
//}
Compilation message
icc.cpp: In function 'bool query3(int, int, std::vector<int>, std::vector<int>)':
icc.cpp:46:9: warning: unused variable 'x' [-Wunused-variable]
46 | int x=0,y=0;
| ^
icc.cpp:46:13: warning: unused variable 'y' [-Wunused-variable]
46 | int x=0,y=0;
| ^
icc.cpp: In function 'ii trace(std::vector<int>, std::vector<int>)':
icc.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
| ~^~~~~~~~~~~~~~
icc.cpp: In function 'ii trace2(std::vector<int>, std::vector<int>)':
icc.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
| ~^~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:106:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
106 | if (p[i]==i) tmp.push_back(i); chan[i].clear(), le[i].clear();
| ^~
icc.cpp:106:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
106 | if (p[i]==i) tmp.push_back(i); chan[i].clear(), le[i].clear();
| ^~~~
icc.cpp:129:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i=mid; i<le[level].size(); i++)
| ~^~~~~~~~~~~~~~~~~
icc.cpp:131:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i=mid; i<chan[level].size(); i++)
| ~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
468 KB |
Ok! 110 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 112 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
512 KB |
Ok! 619 queries used. |
| 2 |
Correct |
30 ms |
508 KB |
Ok! 479 queries used. |
| 3 |
Correct |
45 ms |
468 KB |
Ok! 558 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
516 KB |
Ok! 1569 queries used. |
| 2 |
Correct |
120 ms |
512 KB |
Ok! 1156 queries used. |
| 3 |
Correct |
142 ms |
516 KB |
Ok! 1521 queries used. |
| 4 |
Correct |
118 ms |
528 KB |
Ok! 1481 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
524 KB |
Ok! 1460 queries used. |
| 2 |
Correct |
131 ms |
516 KB |
Ok! 1448 queries used. |
| 3 |
Correct |
116 ms |
520 KB |
Ok! 1393 queries used. |
| 4 |
Correct |
129 ms |
516 KB |
Ok! 1517 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
524 KB |
Ok! 1399 queries used. |
| 2 |
Correct |
140 ms |
528 KB |
Ok! 1398 queries used. |
| 3 |
Correct |
131 ms |
532 KB |
Ok! 1327 queries used. |
| 4 |
Correct |
113 ms |
468 KB |
Ok! 1439 queries used. |
| 5 |
Correct |
123 ms |
516 KB |
Ok! 1547 queries used. |
| 6 |
Correct |
128 ms |
532 KB |
Ok! 1474 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
592 KB |
Ok! 1449 queries used. |
| 2 |
Correct |
109 ms |
520 KB |
Ok! 1210 queries used. |
