| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 810545 | QwertyPi | Mouse (info1cup19_mouse) | C++14 | 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>
#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
int query(vector<int> q);
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