oj.uz

Submission #315071

# Submission time Handle Problem Language Result Execution time Memory
315071 2020-10-22T02:09:11 Z 2qbingxuan Mouse (info1cup19_mouse) C++14
21.2069 / 100
 3000 ms 384 KB 
#ifndef local
#include "grader.h"
#endif // local
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    (std::cerr << "(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#else
#define debug(...) ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;

vector<int> secret_p;
#ifdef local
int qs=0;
int query(vector<int> q) {
    ++qs;
    assert(secret_p.size() == q.size());
    int n = secret_p.size(), cnt = 0;
    for(int i = 0; i < n; i++) if(secret_p[i] == q[i]) ++cnt;
    if(cnt == n) {
        debug(qs);
        cerr << "OK!\n";
        exit(0);
    }
    return cnt;
}
#endif // local

void solve(int n) {
    vector<int> p(n);
    vector<int> ok(n);
    iota(all(p), 1);
    int qp = query(p);
    debug(qp);
    for(int i = 0; i < n; i++) cerr << p[i] << ' ';
    cerr << '\n';
    for(int t = 0; t < n*n; t++) {
        int i = t % n;
        /* vector<int> v; */
        int pos = -1;
        for(int j = 0; j < n; j++) {
            if(j == i) continue;
            /* if(ok[j]) continue; */
            swap(p[i], p[j]);
            int x = query(p) - qp;
            swap(p[i], p[j]);
            if(x > 0) {
                pos = j;
                break;
            }
            /*
            if(x == 2) {
                pos = j;
                break;
            } else if(x == -2) {
                pos = i;
                ok[j] = true;
                break;
            } else if(x == 1) {
                pos = j;
                break;
            } else if(x == -1) {
                v.pb(j);
            } else if(x != 0) {
                cerr << "QQQ\n";
            }
            */
        }
        
        if(pos != -1) {
            swap(p[i], p[pos]);
            qp = query(p);
            /* for(int j: v) ok[j] = true; */
        }
    }
    for(int i = 0; i < n; i++) cerr << p[i] << ' ';
    cerr << '\n';
}

#ifdef local
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    secret_p.resize(n);
    for(int i = 0; i < n; i++) cin >> secret_p[i];
    solve(n);
}
#endif // local

Subtask #1
9.000004 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 28
2 Correct 1 ms 256 KB Correct! Number of queries: 12
3 Correct 1 ms 256 KB Correct! Number of queries: 24
4 Correct 1 ms 384 KB Correct! Number of queries: 56
5 Correct 1 ms 256 KB Correct! Number of queries: 35
6 Correct 1 ms 256 KB Correct! Number of queries: 36

Subtask #2
12.206892 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 28
2 Correct 1 ms 256 KB Correct! Number of queries: 12
3 Correct 1 ms 256 KB Correct! Number of queries: 24
4 Correct 1 ms 384 KB Correct! Number of queries: 56
5 Correct 1 ms 256 KB Correct! Number of queries: 35
6 Correct 1 ms 256 KB Correct! Number of queries: 36
7 Correct 233 ms 384 KB Correct! Number of queries: 5800
8 Correct 226 ms 384 KB Correct! Number of queries: 5000
9 Correct 181 ms 256 KB Correct! Number of queries: 5100
10 Correct 207 ms 372 KB Correct! Number of queries: 5600
11 Correct 136 ms 256 KB Correct! Number of queries: 4100
12 Correct 200 ms 256 KB Correct! Number of queries: 3600
13 Correct 190 ms 256 KB Correct! Number of queries: 5000
14 Correct 221 ms 256 KB Correct! Number of queries: 4500
15 Correct 219 ms 256 KB Correct! Number of queries: 4600
16 Correct 205 ms 256 KB Correct! Number of queries: 3600

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 28
2 Correct 1 ms 256 KB Correct! Number of queries: 12
3 Correct 1 ms 256 KB Correct! Number of queries: 24
4 Correct 1 ms 384 KB Correct! Number of queries: 56
5 Correct 1 ms 256 KB Correct! Number of queries: 35
6 Correct 1 ms 256 KB Correct! Number of queries: 36
7 Correct 233 ms 384 KB Correct! Number of queries: 5800
8 Correct 226 ms 384 KB Correct! Number of queries: 5000
9 Correct 181 ms 256 KB Correct! Number of queries: 5100
10 Correct 207 ms 372 KB Correct! Number of queries: 5600
11 Correct 136 ms 256 KB Correct! Number of queries: 4100
12 Correct 200 ms 256 KB Correct! Number of queries: 3600
13 Correct 190 ms 256 KB Correct! Number of queries: 5000
14 Correct 221 ms 256 KB Correct! Number of queries: 4500
15 Correct 219 ms 256 KB Correct! Number of queries: 4600
16 Correct 205 ms 256 KB Correct! Number of queries: 3600
17 Execution timed out 3018 ms 256 KB Time limit exceeded
18 Halted 0 ms 0 KB -