Submission #810542

# Submission time Handle Problem Language Result Execution time Memory
810542 2023-08-06T10:57:52 Z QwertyPi Mouse (info1cup19_mouse) C++14
Compilation error
0 ms 0 KB
#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);
      |     ^~~~~