oj.uz

Submission #757824

# Submission time Handle Problem Language Result Execution time Memory
757824 2023-06-13T19:06:06 Z taher MalnaRISC (COI21_malnarisc) C++17
100 / 100
 1 ms 340 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct