oj.uz

Submission #1100776

# Submission time Handle Problem Language Result Execution time Memory
1100776 2024-10-14T16:38:04 Z Kirill22 Mouse (info1cup19_mouse) C++17
48 / 100
 140 ms 960 KB 
#include "bits/stdc++.h"

using namespace std;

//#include "debug.h"

int query(vector<int> q);

int get(vector<int> q) {
    for (auto& x : q) {
        x++;
    }
    int res = query(q);
    if (res == (int) q.size()) {
        exit(0);
    }
    return res;
}

mt19937 gen(22);

void solve(int n) {
    if (n == 1) {
        get({1});
        return;
    }
    vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    while (get(p) > 0) {
        std::shuffle(p.begin(), p.end(), gen);
    }
    vector<int> used(n);
    int cur = 0;
//    int iter = 0;
    while (cur < n) {
//        if (iter ++ > 10) break;
        vector<int> need;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                need.push_back(i);
            }
        }
        const int m = (int) need.size();
        vector<vector<pair<int, int>>> qu;
        if (m % 2 == 0) {
            // 0 1 2 3 4 5
            for (int i = 0; i + 1 < m; i++) {
                qu.push_back({{i, m - 1}});
                for (int j = 0; j + 1 < m; j++) {
                    if (j == i) {
                        continue;
                    }
                    int j2 = 2 * i - j;
                    j2 %= (m - 1);
                    j2 += m - 1;
                    j2 %= m - 1;
                    if (j < j2) {
                        qu.back().push_back({j, j2});
                    }
                }
            }
        } else {
            // 0 1 2 3 4 5 6
            for (int i = 0; i < m; i++) {
                qu.push_back({});
                for (int j = 0; j < m; j++) {
                    if (j == i) {
                        continue;
                    }
                    int j2 = 2 * i - j;
                    j2 %= m;
                    j2 += m;
                    j2 %= m;
                    if (j < j2) {
                        qu.back().push_back({j, j2});
                    }
                }
            }
        }
        for (auto& arr : qu) {
            for (auto& [x, y] : arr) {
                x = need[x];
                y = need[y];
            }
        }
//        debug(need, p, cur, qu);
        for (auto& arr : qu) {
            auto q = p;
            for (auto [x, y] : arr) {
                swap(q[x], q[y]);
            }
            int res = get(q);
            if (res > cur) {
                int l = -1, r = (int) arr.size() - 1, value = res;
                while (l + 1 < r) {
                    int m = (l + r) / 2;
                    q = p;
                    for (int i = 0; i <= m; i++) {
                        swap(q[arr[i].first], q[arr[i].second]);
                    }
                    int res2 = get(q);
                    if (res2 > cur) {
                        r = m;
                        value = res2;
                    } else {
                        l = m;
                    }
                }
                auto [x, y] = arr[r];
                if (value - cur == 2) {
                    swap(p[x], p[y]);
                    used[x] = used[y] = 1;
                } else {
                    swap(p[x], p[y]);
                    cur = value;
                    int j = 0;
                    while (j < n && (!used[j] || j == x || j == y)) {
                        j++;
                    }
                    if (j < n) {
                        q = p;
                        swap(q[x], q[j]);
                        value = get(q);
                        if (cur - value == 2) {
                            used[x] = 1;
                        } else {
                            used[y] = 1;
                        }
                    } else {
                        j = 0;
                        while (j == x || j == y) j++;
                        q = p;
                        swap(q[x], q[j]);
                        value = get(q);
                        if (cur - value == 1) {
                            used[x] = 1;
                        } else {
                            used[y] = 1;
                        }
                    }
                }
                break;
            }
        }
        cur = std::accumulate(used.begin(), used.end(), 0);
    }
    get(p);
}

//vector<int> want = {1, 5, 3, 4, 2};
//
//int query(vector<int> q) {
//    for (auto& x : q) {
//        cout << x << " ";
//    }
//    cout << endl;
//    int cnt = 0;
//    for (int i = 0; i < (int) q.size(); i++) {
//        cnt += q[i] == want[i];
//    }
//    return cnt;
//}
//
//int main() {
//    solve(want.size());
//}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 19
2 Correct 1 ms 336 KB Correct! Number of queries: 7
3 Correct 1 ms 336 KB Correct! Number of queries: 13
4 Correct 1 ms 336 KB Correct! Number of queries: 16
5 Correct 1 ms 336 KB Correct! Number of queries: 9
6 Correct 1 ms 336 KB Correct! Number of queries: 19

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 19
2 Correct 1 ms 336 KB Correct! Number of queries: 7
3 Correct 1 ms 336 KB Correct! Number of queries: 13
4 Correct 1 ms 336 KB Correct! Number of queries: 16
5 Correct 1 ms 336 KB Correct! Number of queries: 9
6 Correct 1 ms 336 KB Correct! Number of queries: 19
7 Correct 6 ms 336 KB Correct! Number of queries: 500
8 Correct 4 ms 336 KB Correct! Number of queries: 400
9 Correct 5 ms 336 KB Correct! Number of queries: 400
10 Correct 4 ms 336 KB Correct! Number of queries: 400
11 Correct 3 ms 336 KB Correct! Number of queries: 300
12 Correct 4 ms 336 KB Correct! Number of queries: 400
13 Correct 4 ms 504 KB Correct! Number of queries: 400
14 Correct 4 ms 336 KB Correct! Number of queries: 400
15 Correct 4 ms 336 KB Correct! Number of queries: 400
16 Correct 5 ms 336 KB Correct! Number of queries: 400

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 19
2 Correct 1 ms 336 KB Correct! Number of queries: 7
3 Correct 1 ms 336 KB Correct! Number of queries: 13
4 Correct 1 ms 336 KB Correct! Number of queries: 16
5 Correct 1 ms 336 KB Correct! Number of queries: 9
6 Correct 1 ms 336 KB Correct! Number of queries: 19
7 Correct 6 ms 336 KB Correct! Number of queries: 500
8 Correct 4 ms 336 KB Correct! Number of queries: 400
9 Correct 5 ms 336 KB Correct! Number of queries: 400
10 Correct 4 ms 336 KB Correct! Number of queries: 400
11 Correct 3 ms 336 KB Correct! Number of queries: 300
12 Correct 4 ms 336 KB Correct! Number of queries: 400
13 Correct 4 ms 504 KB Correct! Number of queries: 400
14 Correct 4 ms 336 KB Correct! Number of queries: 400
15 Correct 4 ms 336 KB Correct! Number of queries: 400
16 Correct 5 ms 336 KB Correct! Number of queries: 400
17 Runtime error 140 ms 960 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -