Submission #810581

#	Time	Username	Problem	Language	Result	Execution time	Memory
810581		QwertyPi	Mouse (info1cup19_mouse)	C++14	69.23 / 100	59 ms	304 KiB

mouse

#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){
    assert(!success);
    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); if(done) return;
    binary_search(x, q, sz, m, r, s, vr); if(done) return;
}
 
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)){
        if(s == 1) break;
        if(s == N) return;
        random_shuffle(q, 1);
    }
    
    while(x.size() > 2){
        int sz = x.size();
        int s;
        while(s = query(q), s != n - sz + 1) {
           if(s == n) return;
            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;
        }
        s = query(q); if(s == n) return;
        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) return;
        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 (stderr)

mouse.cpp: In function 'void random_shuffle(std::vector<int>&, int)':
mouse.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     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:62:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |     while(s = query(q)){
      |           ~~^~~~~~~~~~
mouse.cpp:88:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   88 |     while(s = query(q)){
      |           ~~^~~~~~~~~~
mouse.cpp:99: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]
   99 |             for(int i = 1; i < x.size(); i++) swap(x[i].second, x[rng() % i + 1].second);
      |                            ~~^~~~~~~~~~
mouse.cpp:100: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]
  100 |             for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
      |                            ~~^~~~~~~~~~
mouse.cpp:116:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  116 |         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:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  116 |         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:119: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]
  119 |         for(int i = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
      |                        ~~^~~~~~~~~~

• Subtask 1: 9.000004 / 13
• Subtask 2: 26.307704 / 38
• Subtask 3: 33.923092000000004 / 49