oj.uz

답안 #810547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810547 2023-08-06T10:59:07 Z QwertyPi Mouse (info1cup19_mouse) C++14
9 / 100
 5 ms 300 KB 
#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 < 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]);
    }

    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;
      |                        ~~^~~~~~~~~~

Subtask #1
9.000004 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Correct! Number of queries: 62
2 Correct 0 ms 208 KB Correct! Number of queries: 7
3 Correct 1 ms 208 KB Correct! Number of queries: 42
4 Correct 1 ms 208 KB Correct! Number of queries: 65
5 Correct 1 ms 208 KB Correct! Number of queries: 66
6 Correct 1 ms 208 KB Correct! Number of queries: 122

Subtask #2
0.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Correct! Number of queries: 62
2 Correct 0 ms 208 KB Correct! Number of queries: 7
3 Correct 1 ms 208 KB Correct! Number of queries: 42
4 Correct 1 ms 208 KB Correct! Number of queries: 65
5 Correct 1 ms 208 KB Correct! Number of queries: 66
6 Correct 1 ms 208 KB Correct! Number of queries: 122
7 Correct 4 ms 208 KB Correct! Number of queries: 400
8 Correct 5 ms 208 KB Correct! Number of queries: 400
9 Correct 3 ms 208 KB Correct! Number of queries: 300
10 Correct 4 ms 208 KB Correct! Number of queries: 400
11 Correct 4 ms 208 KB Correct! Number of queries: 300
12 Runtime error 4 ms 208 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 300 KB Correct! Number of queries: 62
2 Correct 0 ms 208 KB Correct! Number of queries: 7
3 Correct 1 ms 208 KB Correct! Number of queries: 42
4 Correct 1 ms 208 KB Correct! Number of queries: 65
5 Correct 1 ms 208 KB Correct! Number of queries: 66
6 Correct 1 ms 208 KB Correct! Number of queries: 122
7 Correct 4 ms 208 KB Correct! Number of queries: 400
8 Correct 5 ms 208 KB Correct! Number of queries: 400
9 Correct 3 ms 208 KB Correct! Number of queries: 300
10 Correct 4 ms 208 KB Correct! Number of queries: 400
11 Correct 4 ms 208 KB Correct! Number of queries: 300
12 Runtime error 4 ms 208 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -