oj.uz

답안 #810553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810553 2023-08-06T11:02:46 Z QwertyPi Mouse (info1cup19_mouse) C++14
34 / 100
 129 ms 304 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){
        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:78:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   78 |     while(s = query(q) != 1){
      |           ~~^~~~~~~~~~~~~~~
mouse.cpp:88: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]
   88 |             for(int i = 1; i < x.size(); i++) swap(x[i].second, x[rng() % i + 1].second);
      |                            ~~^~~~~~~~~~
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 = 0; i < x.size(); i++) q[x[i].first] = x[i].second;
      |                            ~~^~~~~~~~~~
mouse.cpp:109:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |         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:109:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |         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:112: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]
  112 |         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 208 KB Correct! Number of queries: 63
2 Correct 0 ms 208 KB Correct! Number of queries: 3
3 Correct 1 ms 208 KB Correct! Number of queries: 43
4 Correct 1 ms 208 KB Correct! Number of queries: 45
5 Correct 1 ms 208 KB Correct! Number of queries: 63
6 Correct 1 ms 208 KB Correct! Number of queries: 123

Subtask #2
25.00001 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Correct! Number of queries: 63
2 Correct 0 ms 208 KB Correct! Number of queries: 3
3 Correct 1 ms 208 KB Correct! Number of queries: 43
4 Correct 1 ms 208 KB Correct! Number of queries: 45
5 Correct 1 ms 208 KB Correct! Number of queries: 63
6 Correct 1 ms 208 KB Correct! Number of queries: 123
7 Correct 4 ms 208 KB Correct! Number of queries: 500
8 Correct 5 ms 208 KB Correct! Number of queries: 400
9 Correct 3 ms 220 KB Correct! Number of queries: 400
10 Correct 5 ms 208 KB Correct! Number of queries: 400
11 Correct 4 ms 208 KB Correct! Number of queries: 300
12 Correct 4 ms 208 KB Correct! Number of queries: 400
13 Correct 2 ms 208 KB Correct! Number of queries: 400
14 Correct 10 ms 208 KB Correct! Number of queries: 800
15 Correct 7 ms 208 KB Correct! Number of queries: 1000
16 Correct 11 ms 208 KB Correct! Number of queries: 900

Subtask #3
0.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Correct! Number of queries: 63
2 Correct 0 ms 208 KB Correct! Number of queries: 3
3 Correct 1 ms 208 KB Correct! Number of queries: 43
4 Correct 1 ms 208 KB Correct! Number of queries: 45
5 Correct 1 ms 208 KB Correct! Number of queries: 63
6 Correct 1 ms 208 KB Correct! Number of queries: 123
7 Correct 4 ms 208 KB Correct! Number of queries: 500
8 Correct 5 ms 208 KB Correct! Number of queries: 400
9 Correct 3 ms 220 KB Correct! Number of queries: 400
10 Correct 5 ms 208 KB Correct! Number of queries: 400
11 Correct 4 ms 208 KB Correct! Number of queries: 300
12 Correct 4 ms 208 KB Correct! Number of queries: 400
13 Correct 2 ms 208 KB Correct! Number of queries: 400
14 Correct 10 ms 208 KB Correct! Number of queries: 800
15 Correct 7 ms 208 KB Correct! Number of queries: 1000
16 Correct 11 ms 208 KB Correct! Number of queries: 900
17 Correct 58 ms 208 KB Correct! Number of queries: 2500
18 Correct 53 ms 304 KB Correct! Number of queries: 2200
19 Correct 53 ms 208 KB Correct! Number of queries: 2500
20 Correct 52 ms 304 KB Correct! Number of queries: 2400
21 Correct 56 ms 208 KB Correct! Number of queries: 2500
22 Correct 52 ms 300 KB Correct! Number of queries: 2400
23 Correct 49 ms 208 KB Correct! Number of queries: 2100
24 Runtime error 129 ms 296 KB Execution killed with signal 13
25 Halted 0 ms 0 KB -