Submission #1229189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229189		avighna	Art Collections (BOI22_art)	C++20	50 / 100	385 ms	440 KiB

art

#include <bits/stdc++.h>

int publish(std::vector<int>);

void answer(std::vector<int>);

void solve(int N) {
  std::vector<int> p(N);
  std::iota(p.begin(), p.end(), 1);
  auto sort = [&](auto &&self, int l, int r) {
    if (l == r) {
      return;
    }
    int m = (l + r) / 2;
    self(self, l, m);
    self(self, m + 1, r);
    int i = l, j = m + 1;
    std::vector<int> t(r - l + 1);
    int idx = 0;
    int init = publish(p);
    while (i <= m and j <= r) {
      std::swap(p[i], p[j]);
      int after = publish(p);
      std::swap(p[i], p[j]);
      t[idx++] = init < after ? p[i++] : p[j++];
    }
    while (i <= m) {
      t[idx++] = p[i++];
    }
    while (j <= r) {
      t[idx++] = p[j++];
    }
    for (int i = 0; i < t.size(); ++i) {
      p[l + i] = t[i];
    }
  };
  sort(sort, 0, N - 1);
  answer(p);
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30