Submission #810557

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810557	2023-08-06T11:05:06 Z	QwertyPi	Mouse (info1cup19_mouse)	C++14	Compilation error	0 ms	0 KB

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){
    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 < 100; 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]);
    }

    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<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 = 0; i < v.size(); i++) swap(v[i], v[rng() % (i + 1)]);
      |                    ~~^~~~~~~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:79:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   79 |     while(s = query(q) != 1){
      |           ~~^~~~~~~~~~~~~~~
mouse.cpp:89: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]
   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: 'int' and 'std::vector<std::pair<int, 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: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: 'int' and 'std::vector<std::pair<int, 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;
      |                        ~~^~~~~~~~~~
/usr/bin/ld: /tmp/cczqOmCe.o: in function `binary_search(std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >&, std::vector<int, std::allocator<int> >&, int, int, int, int, int)':
mouse.cpp:(.text+0x4ac): undefined reference to `query(std::vector<int, std::allocator<int> >&)'
/usr/bin/ld: /tmp/cczqOmCe.o: in function `solve(int)':
mouse.cpp:(.text+0x6d3): undefined reference to `query(std::vector<int, std::allocator<int> >&)'
/usr/bin/ld: mouse.cpp:(.text+0x7b8): undefined reference to `query(std::vector<int, std::allocator<int> >&)'
/usr/bin/ld: mouse.cpp:(.text+0x903): undefined reference to `query(std::vector<int, std::allocator<int> >&)'
/usr/bin/ld: mouse.cpp:(.text+0x97c): undefined reference to `query(std::vector<int, std::allocator<int> >&)'
/usr/bin/ld: /tmp/cczqOmCe.o:mouse.cpp:(.text+0xa4e): more undefined references to `query(std::vector<int, std::allocator<int> >&)' follow
collect2: error: ld returned 1 exit status