Submission #945236

#	Time	Username	Problem	Language	Result	Execution time	Memory
945236		vjudge1	Secret Permutation (RMI19_permutation)	C++17	100 / 100	706 ms	452 KiB

permutation

#include <bits/stdc++.h>

#include "permutation.h"
using namespace std;

mt19937 rng(1234);

#define next amongus
pair<int, int> next[434];
int p[333];
int n;
vector<int> id;

void output() {
        vector<int> res(n);
        for (int i = 1; i <= n; i++) res[p[i] - 1] = i;
        answer(res);
        return;
}

bool Try(int i, int index, int cur) {
        int x = next[index].first;
        int d = next[index].second;
        if (i == n - 1) {
                if (cur + d <= n && p[cur + d] == x) return output(), 1;
                if (cur - d >= 1 && p[cur - d] == x) return output(), 1;
                return 0;
        }

        int random = rng() & 1;
        int t = 2;
        while (t--) {
                if (random) {
                        if (cur + d <= n && p[cur + d] == 0) {
                                p[cur + d] = x;
                                if (Try(i + 1, x, cur + d)) return 1;
                                p[cur + d] = 0;
                        }
                } else {
                        if (cur - d >= 1 && p[cur - d] == 0) {
                                p[cur - d] = x;
                                if (Try(i + 1, x, cur - d)) return 1;
                                p[cur - d] = 0;
                        }
                }
                random ^= 1;
        }
        return 0;
}

void solve(int N) {
        n = N;
        id = vector<int>(N);
        iota(id.begin(), id.end(), 1);
        shuffle(id.begin(), id.end(), rng);
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
                a[i] = query(id);
                id.emplace_back(id[0]);
                id.erase(id.begin());
        }
        int64_t sum = accumulate(a.begin(), a.end(), 0ll);
        sum /= N - 1;
        for (int i = 0; i < N; i++) {
                /// diff between p[id[i]] and p[id[i - 1]]
                next[id[i]] = {(id[i ? i - 1 : N - 1]), sum - a[i]};
        }
        for (int i = 1; i <= N; i++) {
                /// try p[id[0]] = i;
                p[i] = id[0];
                if (Try(0, id[0], i)) break;
                p[i] = 0;
        }
}

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: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 50 / 50