제출 #1207856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207856		spacewalker	The Collection Game (BOI21_swaps)	C++20	100 / 100	38 ms	536 KiB

swaps

//
// --- 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.
//
#include "swaps.h"
#include <bits/stdc++.h>
#include <ranges>

using namespace std;

// schedule(i, j) == 1 ==> a[i] >= a[j] at the time of visit

pair<vector<int>, vector<int>> split(vector<int> v) {
    int len = v.size();
    vector<int> L(v.begin(), v.begin() + len/2), R(v.begin() + len/2, v.end());
    return {L, R};

}
struct Sorter {
  // rooms is the currently known permutation, in ascending order
  map<int, vector<pair<int, int>>> network;
  int n, n_padded;

  void place_in_round(int round, int i, int j) {
    network[round].emplace_back(i, j);
    cerr << "!! scheduled " << i << " " << j << " in round " << round << endl;
  }

  // all of these functions return the round after these swaps finish
  int sort_arbitrary(int round, vector<int> rooms) {
    int len = rooms.size();
    if (len <= 1) return round;
    vector<int> L(rooms.begin(), rooms.begin() + len/2), R(rooms.begin() + len/2, rooms.end());

    int round_after = sort_arbitrary(round, L);
    int _ = sort_arbitrary(round, R);

    return merge(round_after, L, R);
  }

  int merge(int round, vector<int> l, vector<int> r) {
    cerr << "!! merge " << l.size() << endl;
    int len = l.size();
    assert(l.size() == r.size()); 
    for (int i = 0; i < len; ++i) place_in_round(round, l[i], r[len - 1 - i]);
    // after this round, the circuit places all lower elements in r and upper elements in l
    cerr << " starting layer " << 2 * l.size() << " merge " << endl;
    int merge_until = sort_vshaped(round + 1, r);
    cerr << " layer " << 2 * l.size() << " merge from " << round + 1 << " until " << merge_until << endl;
    return sort_vshaped(round + 1, l);
 }

  // sort a zigzag such that first-(inflection1) and (inflection2)-last do not overlap
  int sort_zigzag(int round, vector<int> rooms) {
    return sort_vshaped(round, rooms);
    // int len = rooms.size();
    // if (len <= 1) return round;
    // for (int i = 0; i < len/2; ++i) place_in_round(round, rooms[i], rooms[len - 1 - i]);
    // auto [L, R] = split(rooms);
    // sort_vshaped(round + 1, L);
    // return sort_vshaped(round + 1, R);
    //
  }
  // sort rooms, assuming it is descending/ascending
  int sort_vshaped(int round, vector<int> rooms) {
    cerr << "sort_vshaped " << round << " " << rooms.size() << endl;
    // this is mental illness
    int len = rooms.size();
    if (len <= 1) return round;
    for (int i = 0; i < len/2; ++i) place_in_round(round, rooms[i], rooms[i+len/2]);
    // after this, the upper elements are all in the first half, the lower elements are all in the second half
    auto [L, R] = split(rooms);
    sort_zigzag(round + 1, L);
    return sort_zigzag(round + 1, R);

  }

  Sorter(int N) : n(N), n_padded(1 << (32 - __builtin_clz(N - 1))) {
    // we create a set of visits that can solve the 60%, and use that to solve the 100%
    vector<int> rooms(n_padded);
    iota(begin(rooms), end(rooms), 0);

    sort_arbitrary(0, rooms);
  }

  vector<int> sort() {
    vector<int> labels(n_padded); iota(begin(labels), end(labels), 1);
    for (auto [round_id, swaps] : network) {
      int swaps_made = 0;
      vector<int> source(swaps.size(), -1);
      for (int qid = 0; qid < swaps.size(); ++qid) {
        auto [i, j] = swaps[qid];
        if (labels[i] <= n && labels[j] <= n) {
          source[qid] = swaps_made++;
          schedule(labels[i], labels[j]);
        }
      }
      vector<int> answers = visit();
      for (int qid = 0; qid < swaps.size(); ++qid) {
        auto [i, j] = swaps[qid];
        if (source[qid] != -1) {
          if (answers[source[qid]] == 0) swap(labels[i], labels[j]);
        } else {
          if (labels[i] <= n) swap(labels[i], labels[j]);
        }
      }
      cerr << "! round " << round_id << " state:";
      for (int v : labels) cerr << " " << v;
      cerr << endl;
    }
    vector<int> ans;
    for (int v : labels) if (v <= n) ans.push_back(v);
    return ans;
  }
};
// # [INPUT] expected: [7, 12, 16, 2, 10, 6, 1, 4, 14, 15, 9, 11, 5, 3, 13, 8]

void solve(int N, int V) {
    // TODO implement this function
    // schedule(1, 2);
    // std::vector<int> v = visit();
    // if (v[0] == 1)
    //     answer({1, 2, 3, 4});
    // else
    //     answer({2, 1, 3, 4});
    
    auto sorter = Sorter(N);
    auto rooms = sorter.sort();
    // reverse(begin(rooms), end(rooms));
    answer(rooms);
}

• 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