Submission #444656

#	Time	Username	Problem	Language	Result	Execution time	Memory
444656		Hegdahl	The Collection Game (BOI21_swaps)	C++17	85 / 100	169 ms	1056 KiB

swaps

#include "swaps.h"
#include <bits/stdc++.h>

#define ar array

using namespace std;
//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<ar<int, 2>> lvls[5000];

int solve_range(int l, int r) {
  int mid = l + (r-l+1)/2;

  int lvl = 0;

  if (l != mid-1) lvl = max(lvl, solve_range(l, mid-1));
  if (r != mid) lvl = max(lvl, solve_range(mid, r));

  cerr << l << ' ' << r << '\n';

  int gap = r-l+1;
  do {
    gap = (gap+1)/2;
    cerr << gap << '\n';

    set<ar<int, 2>> need;
    for (int i = l, j = l+gap; j <= r; ++i, ++j)
      need.insert({i, j});

    while (need.size()) {
      set<int> taken;
      for (auto it = need.begin(); it != need.end();) {
        auto [i, j] = *it;
        if (taken.count(i) || taken.count(j)) {
          ++it;
          continue;
        }
        else {
          lvls[lvl].push_back({i, j});
          taken.insert(i);
          taken.insert(j);
          need.erase(it++);
        }
      }
      ++lvl;
    }
  } while (gap > 1);

  return lvl+1;
}

void solve(int n, int v) {
  vector<int> a(n);
  iota(a.begin(), a.end(), 0);

  int v_needed = solve_range(0, n-1);
  cerr << "used, allowed: "<< v_needed << ' ' << v << '\n';

  for (int lvl = 0; lvl < v_needed; ++lvl) {
    //*
    for (auto [i, j] : lvls[lvl])
      cerr << '(' << i << ' ' << j << ") ";
    cerr << '\n'; // */
    //*
    vector<ar<int, 2>> scheduled;
    for (auto [i, j] : lvls[lvl]) {
      scheduled.push_back({i, j});
      schedule(a[i]+1, a[j]+1);
    }

    auto res = visit();
    for (int I = 0; I < (int)scheduled.size(); ++I) {
      auto [i, j] = scheduled[I];
      if (!res[I]) swap(a[i], a[j]);
    }
  }

  /*
  vector<int> inv(n);
  for (int i = 0; i < n; ++i)
    inv[a[i]] = i+1;*/

  for (int &x : a) ++x;
  answer(a);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 9 / 9
• Subtask 6: 6 / 6
• Subtask 7: 9 / 9
• Subtask 8: 6 / 6
• Subtask 9: 21 / 21
• Subtask 10: 14 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6