oj.uz

Submission #1100778

# Submission time Handle Problem Language Result Execution time Memory
1100778 2024-10-14T16:52:38 Z Kirill22 Mouse (info1cup19_mouse) C++17
83.2308 / 100
 91 ms 848 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> ans(n);
    vector<vector<pair<int, int>>> qu;
    if (n % 2 == 0) {
        // 0 1 2 3 4 5
        for (int i = 0; i + 1 < n; i++) {
            qu.push_back({{i, n - 1}});
            for (int j = 0; j + 1 < n; j++) {
                if (j == i) {
                    continue;
                }
                int j2 = 2 * i - j;
                j2 %= (n - 1);
                j2 += n - 1;
                j2 %= n - 1;
                if (j < j2) {
                    qu.back().push_back({j, j2});
                }
            }
        }
    } else {
        // 0 1 2 3 4 5 6
        for (int i = 0; i < n; i++) {
            qu.push_back({});
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    continue;
                }
                int j2 = 2 * i - j;
                j2 %= n;
                j2 += n;
                j2 %= n;
                if (j < j2) {
                    qu.back().push_back({j, j2});
                }
            }
        }
    }
//        debug(need, p, cur, qu);
    for (auto& arr : qu) {
        auto dfs = [&] (auto&& self, int l, int r) {
            auto q = p;
            for (int i = l; i < r; i++) {
                swap(q[arr[i].first], q[arr[i].second]);
            }
            int res = get(q);
            if (!res) {
                return;
            }
            if (l + 1 == r) {
                auto [x, y] = arr[l];
                if (res == 2) {
                    ans[x] = p[y];
                    ans[y] = p[x];
                } else {
                    auto q = p;
                    swap(q[x], q[y]);
                    int j = 0;
                    while (j == x || j == y) j++;
                    swap(q[x], q[j]);
                    int value = get(q);
                    if (value != 0) {
                        ans[y] = p[x];
                    } else {
                        ans[x] = p[y];
                    }
                }
                return;
            }
            int m = (l + r) / 2;
            self(self, l, m);
            self(self, m, r);
        };
        dfs(dfs, 0, arr.size());
    }
    get(ans);
//    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);
//        vector<pair<int, int>> update;
//        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) {
//                    update.push_back({x, y});
//                    update.push_back({y, x});
////                    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: 32
2 Correct 1 ms 336 KB Correct! Number of queries: 13
3 Correct 1 ms 336 KB Correct! Number of queries: 27
4 Correct 1 ms 336 KB Correct! Number of queries: 32
5 Correct 1 ms 336 KB Correct! Number of queries: 26
6 Correct 1 ms 336 KB Correct! Number of queries: 35

Subtask #2
31.99999 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 32
2 Correct 1 ms 336 KB Correct! Number of queries: 13
3 Correct 1 ms 336 KB Correct! Number of queries: 27
4 Correct 1 ms 336 KB Correct! Number of queries: 32
5 Correct 1 ms 336 KB Correct! Number of queries: 26
6 Correct 1 ms 336 KB Correct! Number of queries: 35
7 Correct 5 ms 336 KB Correct! Number of queries: 600
8 Correct 5 ms 336 KB Correct! Number of queries: 500
9 Correct 6 ms 336 KB Correct! Number of queries: 500
10 Correct 7 ms 336 KB Correct! Number of queries: 600
11 Correct 4 ms 336 KB Correct! Number of queries: 500
12 Correct 7 ms 336 KB Correct! Number of queries: 500
13 Correct 4 ms 336 KB Correct! Number of queries: 500
14 Correct 6 ms 336 KB Correct! Number of queries: 500
15 Correct 6 ms 336 KB Correct! Number of queries: 500
16 Correct 5 ms 336 KB Correct! Number of queries: 600

Subtask #3
38.23078 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct! Number of queries: 32
2 Correct 1 ms 336 KB Correct! Number of queries: 13
3 Correct 1 ms 336 KB Correct! Number of queries: 27
4 Correct 1 ms 336 KB Correct! Number of queries: 32
5 Correct 1 ms 336 KB Correct! Number of queries: 26
6 Correct 1 ms 336 KB Correct! Number of queries: 35
7 Correct 5 ms 336 KB Correct! Number of queries: 600
8 Correct 5 ms 336 KB Correct! Number of queries: 500
9 Correct 6 ms 336 KB Correct! Number of queries: 500
10 Correct 7 ms 336 KB Correct! Number of queries: 600
11 Correct 4 ms 336 KB Correct! Number of queries: 500
12 Correct 7 ms 336 KB Correct! Number of queries: 500
13 Correct 4 ms 336 KB Correct! Number of queries: 500
14 Correct 6 ms 336 KB Correct! Number of queries: 500
15 Correct 6 ms 336 KB Correct! Number of queries: 500
16 Correct 5 ms 336 KB Correct! Number of queries: 600
17 Correct 91 ms 848 KB Correct! Number of queries: 3700
18 Correct 80 ms 592 KB Correct! Number of queries: 3600
19 Correct 86 ms 756 KB Correct! Number of queries: 3600
20 Correct 88 ms 592 KB Correct! Number of queries: 3700
21 Correct 89 ms 760 KB Correct! Number of queries: 3600
22 Correct 79 ms 592 KB Correct! Number of queries: 3500
23 Correct 80 ms 592 KB Correct! Number of queries: 3600
24 Correct 83 ms 592 KB Correct! Number of queries: 3800
25 Correct 87 ms 592 KB Correct! Number of queries: 3800
26 Correct 88 ms 592 KB Correct! Number of queries: 3700