# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
930870 | daoquanglinh2007 | Mouse (info1cup19_mouse) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector <int> adj[305], circuit;
bool vis[305];
void dfs(int u){
vis[u] = 1;
circuit.push_back(u);
for (int v : adj[u]){
if (vis[v]) continue;
dfs(v);
}
}
void findPermutation(int n){
vector <int> q = {};
for (int i = 1; i <= n; i++){
q.push_back(i);
adj[i].clear();
}
while (true){
shuffle(q.begin(), q.end(), rng);
int tmp = query(q);
if (tmp == n) return;
if (tmp == 0) break;
}
for (int t = 1; t <= n; t++){
vector <pii> arr = {};
for (int i = 1; i <= n; i++){
int j = ((t-1-i+3)%n+n)%n;
if (j == 0) j = n;
if (i < j) arr.push_back(mp(i, j));
}
vector <int> q2 = q;
for (pii p : arr) swap(q2[p.fi-1], q2[p.se-1]);
int num = query(q2);
if (num == n) return;
int cur = -1;
for (int i = 1; i <= num; i++){
int l = cur+1, r = isz(arr)-2, res = isz(arr)-1;
while (l <= r){
int mid = (l+r)/2;
q2 = q;
for (int j = 0; j <= mid; j++)
swap(q2[arr[j].fi-1], q2[arr[j].se-1]);
if (query(q2) >= i){
res = mid;
r = mid-1;
}
else l = mid+1;
}
adj[arr[res].fi].push_back(arr[res].se);
adj[arr[res].se].push_back(arr[res].fi);
cur = res;
}
}
vector <int> p = q;
memset(vis, 0, sizeof(vis));
for (int u = 1; u <= n; u++){
if (vis[u]) continue;
circuit.clear();
dfs(u);
vector <int> q2 = q;
for (int i = 0; i < isz(circuit); i++){
int j = (i+1)%isz(circuit);
q2[circuit[j]-1] = q[circuit[i]-1];
}
int tmp = query(q2);
if (tmp == n) return;
if (tmp < isz(circuit)) reverse(circuit.begin(), circuit.end());
for (int i = 0; i < isz(circuit); i++){
int j = (i+1)%isz(circuit);
p[circuit[j]-1] = q[circuit[i]-1];
}
}
query(p);
}