Submission #807546

#	Time	Username	Problem	Language	Result	Execution time	Memory
807546		dong_liu	The Collection Game (BOI21_swaps)	C++17	100 / 100	5 ms	424 KiB

swaps

/*
https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
*/
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) static_cast<int>(v.size())
#define all(v) (v).begin(), (v).end()
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<int> vi;

#if 0

void solve(int n, int v);
void schedule(int i, int j);
vi visit();
void answer(vi v);

#else

#include "swaps.h"

#endif

void solve(int n, int v) {
  vi p(n);
  iota(all(p), 1);

  vector<pair<int, int>> t;
  auto sch = [&](int i, int j) {
    schedule(p[i], p[j]);
    t.push_back({i, j});
  };
  auto vis = [&]() {
    if (sz(t)) {
      vi v = visit();
      for (int h = 0; h < sz(t); h++)
        if (!v[h]) {
          auto [i, j] = t[h];
          swap(p[i], p[j]);
        }
      t.clear();
    }
  };
  for (int p = 1; p < n; p *= 2)
    for (int k = p; k >= 1; k /= 2) {
      for (int j = k % p; j < n - k; j += k * 2)
        for (int i = 0; i < min(k, n - j - k); i++)
          if ((i + j) / (p * 2) == (i + j + k) / (p * 2)) sch(i + j, i + j + k);
      vis();
    }
  answer(p);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 14 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 6 / 6