#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
static const int N=500;
static bool done;
static int n;
int fake_query(vector<int> Q){
if (done) return 0;
int tmp=query(Q);
if (tmp==n) done=1;
return tmp;
}
static mt19937 rng(69420);
vector<vector<pair<int, int>>> round_robin(int m){
vector<int> v(m+(m&1));
iota(v.begin(), v.end(), 0);
vector<vector<pair<int, int>>> ans;
int cnt=m+(m&1)-1;
for (int i=0; i<cnt; ++i){
ans.emplace_back();
for (int j=0; j<(int)v.size()/2; ++j){
int x=v[j], y=v[(int)v.size()-j-1];
if (x<m && y<m) ans.back().emplace_back(x, y);
}
v.insert(v.begin()+1, v.back());
v.pop_back();
}
return ans;
}
static vector<int> g[N];
static int vis[N];
static vector<int> path, cycle;
void dfs(int u, int p){
path.push_back(u);
vis[u]=1;
bool pp=0;
for (int v:g[u]){
if (v==p && !pp){
pp=1;
continue;
}
if (vis[v]){
if (cycle.empty()) cycle=path;
}else dfs(v, u);
}
path.pop_back();
}
void findPermutation(int _n) {
n=_n;
vector<int> p(n);
vector<int> mark(n);
iota(p.begin(), p.end(), 1);
while (fake_query(p)) shuffle(p.begin(), p.end(), rng);
auto order=round_robin(n);
auto get_swapped=[&](const vector<pair<int, int>> &v, int pos) -> vector<int> {
auto q=p;
for (int i=0; i<=pos; ++i) swap(q[v[i].first], q[v[i].second]);
return q;
};
vector<pair<int, int>> edges;
for (auto &i:order){
int pos=(int)i.size()-1, cnt=fake_query(get_swapped(i, pos));
while (cnt){
int l=0, r=pos-1;
int prv=-1;
while (l<=r){
int mid=(l+r)>>1;
int tmp=fake_query(get_swapped(i, mid));
if (tmp==cnt) r=mid-1;
else l=mid+1, prv=tmp;
}
if (prv==-1) prv=fake_query(get_swapped(i, r));
edges.push_back(i[l]);
if (cnt-prv==2) edges.push_back(i[l]);
pos=r;
cnt=prv;
}
}
for (auto &i:edges){
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
auto get_shifted=[&](const vector<int> &cyc) -> vector<int> {
auto q=p;
int tmp=q[cyc[0]];
for (int i=0; i<(int)cyc.size()-1; ++i) q[cyc[i]]=q[cyc[i+1]];
q[cyc.back()]=tmp;
return q;
};
vector<int> ans=p;
auto shift=[&](const vector<int> &cyc) -> void {
int tmp=ans[cyc[0]];
for (int i=0; i<(int)cyc.size()-1; ++i) ans[cyc[i]]=ans[cyc[i+1]];
ans[cyc.back()]=tmp;
};
for (int i=0; i<n; ++i) if (!vis[i]){
cycle.clear();
dfs(i, -1);
if ((int)cycle.size()>=2){
int tmp=fake_query(get_shifted(cycle));
if (tmp) shift(cycle);
else{
reverse(cycle.begin(), cycle.end());
shift(cycle);
}
tmp=fake_query(get_shifted(cycle));
}
}
fake_query(ans);
}
Compilation message
mouse.cpp:1:10: fatal error: perm.h: No such file or directory
1 | #include "perm.h"
| ^~~~~~~~
compilation terminated.
