Submission #1296934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296934		MisterReaper	Secret Permutation (RMI19_permutation)	C++20	93.33 / 100	2871 ms	444 KiB

permutation

#include "permutation.h"
#include "bits/stdc++.h"

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

namespace {
    std::random_device rd;
    std::mt19937 rng(rd());

    int sumf(std::vector<int> p, std::vector<int> v) {
        int n = int(p.size());
        int res = 0;
        for (int i = 0; i + 1 < n; ++i) {
            res += std::abs(p[v[i]] - p[v[i + 1]]);
        }
        return res;
    }
};

void solve(int N) {
    // if (N == 2) {
    //     std::vector<int> V = {1, 2};
    //     int qAns = query(V);
    //     if (qAns == 1) {
    //         std::vector<int> P = {1, 2};
    //         answer(P);
    //     }
    // }

    std::vector<int> p(N);
    std::iota(p.begin(), p.end(), 0);

    std::shuffle(p.begin(), p.end(), rng);

    debug(p);

    i64 sum = 0;
    std::vector<int> dif(N);
    for (int i = 0; i < N; ++i) {
        auto ap = p;
        for (int j = 0; j < N; ++j) {
            ap[j] += 1;
        }
        dif[i] = query(ap);
        sum += dif[i];
        std::rotate(p.begin(), p.begin() + 1, p.end());
    }

    debug(dif);
    debug(sum);

    sum /= N - 1;

    for (int i = 0; i < N; ++i) {
        dif[i] = sum - dif[i];
    }

    debug(dif);

    std::vector<int> visglobal(4 * N + 1);

    auto vis = visglobal.begin() + 2 * N;

    std::vector<int> cur(N);
    std::vector<std::vector<int>> ans;
    auto dfs = [&](auto&& self, int i, int mn, int mx, int now) -> void {
        if (mx - mn > N - 1) {
            return;
        }
        if (i == N) {
            if (now + dif[0] != 0 && now - dif[0] != 0) {
                return;
            }
            int mnval = *std::min_element(cur.begin(), cur.end());
            std::vector<int> normal_cur(N);
            for (int j = 0; j < N; ++j) {
                normal_cur[j] = cur[j] - mnval + 1;
            }
            debug(normal_cur);
            ans.emplace_back(normal_cur);
            return;
        }

        for (int iter = 0; iter < 2; ++iter) {
            assert(-2 * N <= now + dif[i] && now + dif[i] <= 2 * N);
            if (!vis[now + dif[i]]) {
                cur[p[i]] = now + dif[i];
                vis[now + dif[i]] = true;
                self(self, i + 1, std::min(mn, now + dif[i]), std::max(mx, now + dif[i]), now + dif[i]);
                vis[now + dif[i]] = false;
            }
            dif[i] *= -1;
        }
    };
    cur[p[0]] = 0;
    vis[0] = true;
    dfs(dfs, 1, 0, 0, 0);

    assert(!ans.empty());

    std::cerr << ans.size() << '\n';

    debug(ans);

    while (ans.size() > 2) {
        std::cerr << ans.size() << '\n';
        debug("extra");
        std::shuffle(p.begin(), p.end(), rng);
        auto ap = p;
        for (int i = 0; i < N; ++i) {
            ap[i] += 1;
        }
        i64 res = query(ap);
        std::vector<std::vector<int>> real;
        for (auto ansp : ans) {
            if (res == sumf(ansp, p)) {
                real.emplace_back(ansp);
            }
        }
        ans = std::move(real);
    }

    assert(!ans.empty());

    debug(ans);

    for (auto ansp : ans) {
        debug(ansp);
        answer(ansp);
    }

    debug("not found");
}

Compilation message (stderr)

stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   fscanf(stdin, "%d", &x);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 15
• Subtask 2: 32.6667 / 35
• Subtask 3: 46.6666 / 50