#include<bits/stdc++.h>
//#include "icc.h"
using namespace std;
#define ll long long
#define pb push_back
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rnd(seed);
const int maxn = 1e2 + 20;
vector<int> cmp[maxn];
int a[maxn] , b[maxn] , where[maxn] , x , y , pt = 1;
/*
int query(int sz1 , int sz2 , int* a , int* b)
{
cout << "START" << endl;
cout << sz1 << " " << sz2 << endl;
for(int i = 0; i < sz1; i++)
cout << a[i] << " ";
cout << endl;
for(int i = 0; i < sz2; i++)
cout << b[i] << " ";
cout << endl;
int t = 0;
for(int i = 0; i < sz1; i++)
t += (a[i] == x || a[i] == y);
if(t != 1)
return 0;
t = 0;
for(int i = 0; i < sz2; i++)
t += (b[i] == x || b[i] == y);
if(t != 1)
return 0;
return 1;
}
void setRoad(int a , int b)
{
cout << a << " " << b << " HOORAY" << endl;
if(pt)
cout << "HERE DONE" << endl;
if(pt)
pt-- , x = 2 , y = 3;
else
exit(0);
}*/
pair<int , int> fn(int n)
{
int pt1 = 0 , pt2 = 0;
while(1)
{
pt1 = 0 , pt2 = 0;
for(int i = 1; i <= n; i++)
{
if(rand() % 2)
{
for(auto x : cmp[i])
a[pt1++] = x;
}
else
{
for(auto x : cmp[i])
b[pt2++] = x;
}
}
if(query(pt1 , pt2 , a , b))
break;
}
vector<int> x , y;
for(int i = 0; i < pt1; i++)
x.pb(a[i]);
for(int i = 0; i < pt2; i++)
y.pb(b[i]);
while((int)y.size() > 1)
{
for(int i = 0; i < (int)y.size() / 2; i++)
b[i] = y[i];
pt2 = y.size() / 2;
if(query(pt1 , pt2 , a , b))
{
y.clear();
for(int i = 0; i < pt2; i++)
y.pb(b[i]);
}
else
{
vector<int> tmp;
for(int i = pt2; i < (int)y.size(); i++)
tmp.pb(y[i]);
y = tmp;
}
}
swap(x , y);
pt1 = x.size();
for(int i = 0; i < pt1; i++)
a[i] = x[i];
while((int)y.size() > 1)
{
for(int i = 0; i < (int)y.size() / 2; i++)
b[i] = y[i];
pt2 = y.size() / 2;
if(query(pt1 , pt2 , a , b))
{
y.clear();
for(int i = 0; i < pt2; i++)
y.pb(b[i]);
}
else
{
vector<int> tmp;
for(int i = pt2; i < (int)y.size(); i++)
tmp.pb(y[i]);
y = tmp;
}
}
setRoad(x[0] , y[0]);
return make_pair(x[0] , y[0]);
}
void run(int n)
{
srand(time(NULL));
for(int i = 1; i <= n; i++)
cmp[i].pb(i) , where[i] = i;
for(int i = 0; i < n - 1; i++)
{
auto tmp = fn(n - i);
int v = tmp.first , u = tmp.second;
int k = where[u];
for(auto x : cmp[k])
where[x] = where[v] , cmp[where[x]].pb(x);
for(int j = k + 1; j <= n - i; j++)
{
for(auto x : cmp[j])
where[x] = j - 1;
cmp[j - 1] = cmp[j];
swap(cmp[j - 1] , cmp[j]);
}
}
}
Compilation message
icc.cpp: In function 'std::pair<int, int> fn(int)':
icc.cpp:76:6: error: 'query' was not declared in this scope
if(query(pt1 , pt2 , a , b))
^~~~~
icc.cpp:92:6: error: 'query' was not declared in this scope
if(query(pt1 , pt2 , a , b))
^~~~~
icc.cpp:118:6: error: 'query' was not declared in this scope
if(query(pt1 , pt2 , a , b))
^~~~~
icc.cpp:133:2: error: 'setRoad' was not declared in this scope
setRoad(x[0] , y[0]);
^~~~~~~
