oj.uz

Submission #420486

# Submission time Handle Problem Language Result Execution time Memory
420486 2021-06-08T11:47:51 Z rama_pang MalnaRISC (COI21_malnarisc) C++17
100 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

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

  int N;
  cin >> N;
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  vector<int> A(N);
  iota(begin(A), end(A), 0);
  shuffle(begin(A), end(A), rnd);

  vector<vector<pair<int, int>>> answer;
  const auto Compare = [&](vector<pair<int, int>> a) {
    answer.emplace_back(a);
    for (auto [x, y] : a) {
      if (x >= N || y >= N) continue;
      if (A[x] > A[y]) swap(A[x], A[y]);
    }
  };

  int n = 1;
  while (n < N) n *= 2;

  vector<vector<int>> sorted;
  for (int i = 0; i < n; i++) {
    sorted.push_back({i});
  }

  for (int len = 1; len < n; len *= 2) {
    vector<pair<int, int>> cmp;
    vector<vector<int>> bitonic;
    for (int i = 0; i < int(sorted.size()); i += 2) {
      int sz = sorted[i].size();
      bitonic.emplace_back(sorted[i + 0]);
      bitonic.emplace_back(sorted[i + 1]);
      for (int x = 0; x < sz; x++) {
        cmp.emplace_back(sorted[i][x], sorted[i + 1][sz - 1 - x]);
      }
    }
    Compare(cmp);
    cmp.clear();
    while (bitonic[0].size() > 1) {
      vector<vector<int>> newBitonic;
      for (int i = 0; i < int(bitonic.size()); i++) {
        int sz = bitonic[i].size();
        newBitonic.emplace_back();
        for (int j = 0; j < sz / 2; j++) newBitonic.back().emplace_back(bitonic[i][j]);
        newBitonic.emplace_back();
        for (int j = sz / 2; j < sz; j++) newBitonic.back().emplace_back(bitonic[i][j]);
      }
      bitonic = newBitonic;
      for (int i = 0; i < int(bitonic.size()); i += 2) {
        int sz = bitonic[i].size();
        for (int x = 0; x < sz; x++) {
          cmp.emplace_back(bitonic[i][x], bitonic[i + 1][x]);
        }
      }
      Compare(cmp);
      cmp.clear();
    }
    vector<vector<int>> newSorted;
    for (int i = 0; i < int(sorted.size()); i += 2) {
      newSorted.emplace_back();
      for (auto x : sorted[i + 0]) newSorted.back().emplace_back(x);
      for (auto x : sorted[i + 1]) newSorted.back().emplace_back(x);
    }
    sorted = newSorted;
  }

  assert(is_sorted(begin(A), end(A)));

  cout << answer.size() << '\n';
  for (auto a : answer) {
    for (auto [x, y] : a) {
      if (x >= N || y >= N) continue;
      cout << "CMPSWP R" << x + 1 << " R" << y + 1 << ' ';
    }
    cout << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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