QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125330#91. Secret PermutationQwerty1232#0 0ms0kbC++201.9kb2023-07-16 15:53:532024-07-04 00:43:31

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 00:43:31]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 15:53:53]
  • 提交

answer

#include <bits/stdc++.h>

#include "permutation.h"

std::mt19937 rnd;

void solve(int n) {
    std::vector<std::vector<int>> all;
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 1);
    do {
        all.push_back(p);
    } while (std::next_permutation(p.begin(), p.end()));

    while (all.size() > 1) {
        std::pair<double, std::vector<int>> min(1e9, {});
        for (int iter = 0; iter < 20; iter++) {
            std::shuffle(p.begin(), p.end(), rnd);
            if (iter < 10) {
                // p = all[iter % all.size()];
                for (int i = 0; i < n; i++) {
                    p[all[iter % all.size()][i] - 1] = i + 1;
                }
            }
            std::vector<int> cum(n * n);

            for (int i = 0; i < all.size(); i++) {
                int sum = 0;
                for (int j = 0; j < n - 1; j++) {
                    sum += abs(all[i][p[j] - 1] - all[i][p[j + 1] - 1]);
                }
                cum[sum]++;
            }

            double cost = 0;
            int cnt = 0;
            for (int i = 0; i < n * n; i++) {
                if (cum[i] > 0) {
                    cost += cum[i] * log2(cum[i]);
                    cnt++;
                }
            }
            min = std::min(min, {cost, p});
        }

        int sum0 = query(p);

        bool suc = false;
        for (int i = 0; i < all.size(); i++) {
            int sum = 0;
            for (int j = 0; j < n - 1; j++) {
                sum += abs(all[i][p[j] - 1] - all[i][p[j + 1] - 1]);
            }
            if (sum != sum0) {
                suc = true;
                all[i] = {};
            }
        }
        if (!suc) {
            break;
        }
        all.erase(std::remove(all.begin(), all.end(), std::vector<int>()), all.end());
    }
    assert(all.size() >= 1);
    answer(all.front());
};

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

7
5 7 1 3 2 4 6

output:

Unauthorized output

result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%