#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef self
vector<int> p;
bool success = false;
int qid = 0;
int query(vector<int> q){
qid++;
// cout << "Query: "; for(auto i : q) cout << i << ' '; cout << ", ";
assert(q.size() == p.size());
int n = p.size();
int ans = 0;
for(int i = 0; i < n; i++){
if(p[i] == q[i]) ans++;
}
// cout << "Ans: " << ans << endl;
if(ans == p.size()) success = true;
return ans;
}
#endif
void random_shuffle(vector<int>& v){
for(int i = 0; i < v.size(); i++) swap(v[i], v[rng() % (i + 1)]);
}
int n;
bool done = false;
vector<int> to_erase;
void binary_search(vector<pair<int, int>>& x, vector<int>& q, int sz, int l, int r, int vl, int vr){
if(vl == vr) return;
if(l + 1 == r){
assert(vl + 1 == vr);
to_erase.push_back(l);
return;
}
int m = (l + r + 1) / 2;
for(int i = 0; i < m; i++){
q[x[i].first] = x[i + 1].second;
}
q[x[m].first] = x[0].second;
for(int i = m + 1; i < sz; i++){
q[x[i].first] = x[i].second;
}
int s = query(q); if(s == n) { done = true; return; }
binary_search(x, q, sz, l, m, vl, s);
binary_search(x, q, sz, m, r, s, vr);
}
void solve(int N){
n = N;
vector<int> q(N); for(int i = 0; i < N; i++) q[i] = i + 1;
int s;
for(int i = 1; i < n; i++){
swap(q[0], q[i]);
int s = query(q);
if(s == n) return;
if(s > 0) {
bool fake = false;
vector<int> r(q.begin(), q.end());
for(int j = 0; j < 20; j++){
for(int i = 1; i < n; i++) swap(r[i], r[1 + rng() % i]);
int s2 = query(r); if(s2 == n) return;
if(s2 == 0) fake = true;
}
if(!fake){
break;
}
}
swap(q[0], q[i]);
}
assert(p[0] == q[0]);
for(int i = 1; i < n; i++) swap(q[i], q[1 + rng() % i]);
while(s = query(q) != 1){
if(s == N) return;
for(int i = 1; i < n; i++) swap(q[i], q[1 + rng() % i]);
}
vector<pair<int, int>> x; for(int i = 0; i < N; i++) x.push_back({i, q[i]});
while(x.size() > 2){
int sz = x.size();
while(query(q) != n - sz + 1) {
for(int i = 1; i < x.size(); i++) swap(x[i].second, x[rng() % i + 1].second);
for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
}
for(int i = 0; i < sz; i++){
q[x[i].first] = x[(i + 1) % sz].second;
}
int s = query(q); if(s == n) break;
int from = n - sz, to = s; int diff = to - from;
if(diff == 0){
for(int i = 1; i < sz - 1; i++){
swap(x[i].second, x[i + 1].second);
}
continue;
}
to_erase.clear();
binary_search(x, q, sz, 0, sz - 1, n - sz, s);
if(done) break;
sort(to_erase.begin(), to_erase.end(), [](auto a, auto b){ return a > b; });
for(int i = 1; i < sz - 1; i++){
swap(x[i].second, x[i + 1].second);
}
for(int i = 0; i < sz; i++) q[x[i].first] = x[i].second; for(auto i : to_erase) x.erase(x.begin() + i);
}
if(x.size() == 1){
for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
int s = query(q); if(s == n) return;
}
query(q);
}
#ifdef self
int32_t main(){
int n; cin >> n; p.resize(n);
for(int i = 0; i < n; i++) cin >> p[i];
solve(n);
if(success){
printf("Success\nNumber of Queries = %lld\n", qid);
}else{
printf("Failed\n");
}
}
#endif
Compilation message
mouse.cpp: In function 'void random_shuffle(std::vector<long long int>&)':
mouse.cpp:27:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i = 0; i < v.size(); i++) swap(v[i], v[rng() % (i + 1)]);
| ~~^~~~~~~~~~
mouse.cpp: In function 'void binary_search(std::vector<std::pair<long long int, long long int> >&, std::vector<long long int>&, long long int, long long int, long long int, long long int, long long int)':
mouse.cpp:48:13: error: 'query' was not declared in this scope
48 | int s = query(q); if(s == n) { done = true; return; }
| ^~~~~
mouse.cpp: In function 'void solve(long long int)':
mouse.cpp:60:17: error: 'query' was not declared in this scope
60 | int s = query(q);
| ^~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from mouse.cpp:1:
mouse.cpp:76:12: error: 'p' was not declared in this scope
76 | assert(p[0] == q[0]);
| ^
mouse.cpp:79:15: error: 'query' was not declared in this scope
79 | while(s = query(q) != 1){
| ^~~~~
mouse.cpp:88:15: error: 'query' was not declared in this scope
88 | while(query(q) != n - sz + 1) {
| ^~~~~
mouse.cpp:89:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 1; i < x.size(); i++) swap(x[i].second, x[rng() % i + 1].second);
| ~~^~~~~~~~~~
mouse.cpp:90:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
| ~~^~~~~~~~~~
mouse.cpp:95:17: error: 'query' was not declared in this scope
95 | int s = query(q); if(s == n) break;
| ^~~~~
mouse.cpp:110:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
110 | for(int i = 0; i < sz; i++) q[x[i].first] = x[i].second; for(auto i : to_erase) x.erase(x.begin() + i);
| ^~~
mouse.cpp:110:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
110 | for(int i = 0; i < sz; i++) q[x[i].first] = x[i].second; for(auto i : to_erase) x.erase(x.begin() + i);
| ^~~
mouse.cpp:113:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
| ~~^~~~~~~~~~
mouse.cpp:114:17: error: 'query' was not declared in this scope
114 | int s = query(q); if(s == n) return;
| ^~~~~
mouse.cpp:116:5: error: 'query' was not declared in this scope
116 | query(q);
| ^~~~~
