Submission #1100779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100779		Kirill22	Mouse (info1cup19_mouse)	C++17	87.77 / 100	102 ms	760 KiB

mouse

#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), used(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);
    std::shuffle(qu.begin(), qu.end(), gen);
    for (auto& arr : qu) {
        vector<pair<int, int>> arr2;
        for (auto [i, j] : arr) {
            if (used[p[i]] && used[p[j]]) {
                //
            } else {
                arr2.push_back({i, j});
            }
        }
        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];
                    used[p[x]] = used[p[y]] = 1;
                } else {
                    if (used[p[x]]) {
                        ans[x] = p[y];
                        used[p[y]] = 1;
                        return;
                    }
                    if (used[p[y]]) {
                        ans[y] = p[x];
                        used[p[x]] = 1;
                        return;
                    }
                    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];
                        used[p[x]] = 1;
                    } else {
                        ans[x] = p[y];
                        used[p[y]] = 1;
                    }
                }
                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 / 13
• Subtask 2: 35.000014 / 38
• Subtask 3: 39.769233 / 49