제출 #757824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757824		taher	MalnaRISC (COI21_malnarisc)	C++17	100 / 100	1 ms	340 KiB

malnarisc

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

bool isPowerOfTwo(int x) {
  while (x > 1) {
    if (x % 2 == 1) {
      return false;
    }
    x /= 2;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;

  int nn = n;
  while (!isPowerOfTwo(nn)) {
    ++nn;
  }
  swap(n, nn);
  vector<vector<array<int, 2>>> ops(60);
  int pos = -1;

  vector<vector<int>> st(n * 4);

  function<void(int, int, int)> Sort = [&](int v, int l, int r) {
    ++pos;
    if (l == r) {
      --pos;
      return ;
    }
    vector<int> x = st[v];

    if ((int) x.size() > 1) {
      for (int i = 0; i < (int) x.size() / 2; i++) {
        if (i + (int) x.size() / 2 < (int) x.size()) {
          ops[pos].push_back({x[i], x[i + (int) x.size() / 2]});
        }
      }
    }
    int mid = l + (r - l) / 2;
    Sort(v * 2, l, mid);
    Sort(v * 2 + 1, mid + 1, r);
    --pos;
    return ;
  };
  
  vector<vector<array<int, 3>>> at(60);

  function<void(int, int, int, int)> Build = [&](int v, int l, int r, int layer) {
    if (l == r) {
      st[v] = {l};
      return ;
    }
    at[layer].push_back({v, l, r});

    int mid = l + (r - l) / 2;
    Build(v * 2, l, mid, layer + 1);
    Build(v * 2 + 1, mid + 1, r, layer + 1);
    merge(st[v * 2].begin(), st[v * 2].end(), st[v * 2 + 1].begin(), st[v * 2 + 1].end(), back_inserter(st[v]));
    return ;
  };
  Build(1, 0, n - 1, 0);

  for (int layer = 59; layer >= 0; layer--) {
    if (at[layer].empty()) {
      continue;
    }

    vector<array<int, 3>> vertices = at[layer];
    for (int i = 0; i < (int) vertices.size(); i++) {
      ++pos;
      int v = vertices[i][0];
      int l = vertices[i][1];
      int r = vertices[i][2];

      vector<int> x = st[v * 2];
      vector<int> y = st[v * 2 + 1];

      int low = (int) x.size() - 1, high = 0;
      while (low >= 0 && high < (int) y.size()) {
        ops[pos].push_back({x[low], y[high]});
        --low;
        ++high;
      }

      if (l < r) {
        int mid = l + (r - l) / 2;
        Sort(v * 2, l, mid);
        Sort(v * 2 + 1, mid + 1, r);
      }
      --pos;
    }
    ++pos;
    while (!ops[pos].empty()) {
      ++pos;
    }
  }

  int sz = 0;
  for (int i = 0; i <= 59; i++) {
    sz += ((int) ops[i].size() > 0);
  }

  cout << sz << '\n';
  for (int i = 0; i <= 59; i++) {
    bool found = false;
    for (int j = 0; j < (int) ops[i].size(); j++) {
      if (ops[i][j][0] < nn && ops[i][j][1] < nn) {
        if (found) {
          cout << " ";
        }
        cout << "CMPSWP " << 'R' << ++ops[i][j][0] << " " << 'R' << ++ops[i][j][1];
        found = true;
      }
    }
    if (found) {
      cout << '\n';
    }
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10