#include <bits/stdc++.h>
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
int query(vector<int> q);
void random_shuffle(vector<int>& v, int f = 0){
for(int i = f; i < v.size(); i++) swap(v[i], v[rng() % (i + 1 - f) + f]);
}
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;
random_shuffle(q);
while(s = query(q)){
if(s == N) return;
random_shuffle(q);
}
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++){
random_shuffle(r, 1);
int s2 = query(r); if(s2 == n) return;
if(s2 == 0) fake = true;
}
if(!fake){
break;
}
}
swap(q[0], q[i]);
}
vector<pair<int, int>> x; for(int i = 0; i < N; i++) x.push_back({i, q[i]});
random_shuffle(q, 1);
while(s = query(q) != 1){
if(s == N) return;
random_shuffle(q, 1);
}
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;
assert(from <= to);
if(diff == 0) 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 = %d\n", qid);
}else{
printf("Failed\n");
}
}
#endif
Compilation message
mouse.cpp: In function 'void random_shuffle(std::vector<int>&, int)':
mouse.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = f; i < v.size(); i++) swap(v[i], v[rng() % (i + 1 - f) + f]);
| ~~^~~~~~~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:61:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
61 | while(s = query(q)){
| ~~^~~~~~~~~~
mouse.cpp:88:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
88 | while(s = query(q) != 1){
| ~~^~~~~~~~~~~~~~~
mouse.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 1; i < x.size(); i++) swap(x[i].second, x[rng() % i + 1].second);
| ~~^~~~~~~~~~
mouse.cpp:97:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
| ~~^~~~~~~~~~
mouse.cpp:113:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
113 | 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:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
113 | 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:116:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 66 |
| 2 |
Correct |
0 ms |
208 KB |
Correct! Number of queries: 32 |
| 3 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 48 |
| 4 |
Runtime error |
1 ms |
208 KB |
Execution killed with signal 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 66 |
| 2 |
Correct |
0 ms |
208 KB |
Correct! Number of queries: 32 |
| 3 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 48 |
| 4 |
Runtime error |
1 ms |
208 KB |
Execution killed with signal 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 66 |
| 2 |
Correct |
0 ms |
208 KB |
Correct! Number of queries: 32 |
| 3 |
Correct |
1 ms |
208 KB |
Correct! Number of queries: 48 |
| 4 |
Runtime error |
1 ms |
208 KB |
Execution killed with signal 13 |
| 5 |
Halted |
0 ms |
0 KB |
- |
