Game

The first line contains one integer ${T}$ denoting the number of test cases ( $1\le T\le 100$ ).
Each of the next ${T}$ lines contains ${24}$ integers denoting Alice's permutation:
• ${40}$ represents Field Marshal
• ${39}$ represents General
• ${38}$ represents Major Generals
• ${37}$ represents Brigadier Generals
• ${36}$ represents Colonels
• ${35}$ represents Majors
• ${34}$ represents Captains
• ${33}$ represents Lieutenants
• ${32}$ represents Engineers
• ${31}$ represents Landmines
• ${30}$ represents Bombs
It is guaranteed that all permutations are chosen uniformly at random and contains exactly the ${24}$ pieces described in the statement.

Output one line for each test case.
If Bob cannot construct the required permutation, print ${-1}$ .
Otherwise, print ${24}$ integers representing Bob's permutation in the same format as in the input. If there are multiple solutions, print any. Bob's permutation must contain exactly the ${24}$ pieces described in the statement.

4 40 39 38 38 37 37 36 36 35 35 34 34 34 33 33 33 32 32 32 31 31 31 30 30 34 31 36 33 31 39 37 38 35 32 32 35 36 31 34 32 38 40 30 33 30 34 33 37 37 30 40 38 36 38 32 34 36 35 37 32 34 33 31 30 33 31 35 34 33 39 31 32 30 33 32 39 37 38 35 40 34 30 31 37 31 33 31 33 34 32 36 36 35 34 32 38

34 36 30 39 33 38 37 31 34 30 33 35 38 31 37 33 40 31 35 32 32 36 32 34 34 32 32 38 40 33 33 30 31 34 31 35 37 32 34 36 33 31 38 30 36 37 35 39 38 33 32 31 36 34 30 34 33 40 32 37 38 30 37 35 33 35 32 31 34 31 39 36 37 34 33 36 34 35 31 38 32 38 31 32 37 30 30 31 33 36 32 33 40 39 34 35

C++11(clang++ 3.9) 解法, 执行用时: 696ms, 内存消耗: 620K, 提交时间: 2020-01-15 16:32:47

#include <bits/stdc++.h>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

const int N = 24;

bool ok;
int a[N], b[N] = {40, 39, 38, 38, 37, 37, 36, 36, 35, 35, 34, 34, 34, 33, 33, 33, 32, 32, 32, 31, 31, 31, 30, 30};
pair<int, pair<int, int>> good[N * N];

int check() {
  int x = 0, y = 0;
  while (x < N && y < N) {
    if (a[x] == b[y] || a[x] == 30 || b[y] == 30) {
      ++x;
      ++y;
    } else if (a[x] == 31)
      ++(b[y] == 32 ? x : y);
    else if (b[y] == 31)
      ++(a[x] == 32 ? y : x);
    else if (a[x] > b[y])
      ++y;
    else
      ++x;
  }
  ok &= y != N;
  return x;
}

int calc() {
  ok = true;
  int ret = 0;
  for (int i = 0; i < N; ++i)
    for (int j = i + 1; j < N; ++j) {
      swap(b[i], b[j]);
      ret += check();
      swap(b[i], b[j]);
    }
  return ret;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<int> uid(0, N - 1);

  int t;
  cin >> t;
  while (t--) {
    for (int i = 0; i < N; ++i) cin >> a[i];
    int cur;
    while ((cur = calc()) < 22 * 23 / 2 * 24) shuffle(b, b + N, rng);
    while (!ok) {
      int i = uid(rng), j = uid(rng);
      swap(b[i], b[j]);
      int tmp = calc();
      if (tmp > cur || ((tmp == cur) && (rng() & 1)) || ok)
        cur = tmp;
      else
        swap(b[i], b[j]);
    }
    for (int i = 0; i < N; ++i) cout << b[i] << ' ';
    cout << '\n';
  }

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
      -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

详情