#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#include <cstring>
#define X first
#define Y second
#define PB push_back
#define DEB 0
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 110;
int n, a[N];
namespace debug {
void init() { for(int i = 0; i < n; ++i) { scanf("%d", a + i); } }
void cmp(int x, int y) { if(a[x] > a[y]) { swap(a[x], a[y]); } }
void check() {
bool ans = 1;
for(int i = 1; i < n; ++i) { ans &= a[i] >= a[i - 1]; }
printf("%s\n", ans ? "success" : "failure");
}
}
struct state {
int lo, hi, d;
state(int lo, int hi, int d) : lo(lo), hi(hi), d(d) {}
};
vector<vector<pii>> out;
vector<vector<state>> prl;
void thread() {
int ind = (int) prl.size() - 1;
prl.PB({});
out.PB({});
for(const state &s : prl[ind]) {
int lo = s.lo, hi = s.hi, mi = (s.lo + s.hi) / 2;
if(lo + 1 != hi && lo < n) {
for(int i = mi; i < min(hi, n); ++i) {
if(s.d == 0) { out[ind].PB({i - (min(hi, n) - mi), i}); }
else { out[ind].PB({i, i - (mi - lo)}); }
}
prl[ind + 1].PB(state(lo, mi, s.d));
prl[ind + 1].PB(state(mi, hi, s.d));
}
}
if(!prl[ind + 1].empty()) { thread(); }
}
int BIO[N];
int main() {
scanf("%d", &n);
if(DEB) debug::init();
prl.PB({});
int cnt_emp = 0;
for(int i = 2; 1; i <<= 1) {
for(int j = 0, f = 0; j < n; j += i, f ^= 1) { prl.back().PB(state(j, j + i, f)); }
thread();
++cnt_emp;
if(i >= n) break;
}
printf("%d\n", (int) out.size() - cnt_emp);
for(int i = 0; i < out.size(); ++i) {
if(out[i].empty()) continue;
memset(BIO, 0, sizeof(BIO));
for(pii p : out[i]) {
printf("CMPSWP R%d R%d ", p.X + 1, p.Y + 1);
assert(!BIO[p.X] && !BIO[p.Y]);
BIO[p.X] = BIO[p.Y] = 1;
if(DEB) { debug::cmp(p.X, p.Y); }
}
printf("\n");
}
if(DEB) debug::check();
return 0;
}
Compilation message
malnarisc.cpp: In function 'int main()':
malnarisc.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < out.size(); ++i) {
| ~~^~~~~~~~~~~~
malnarisc.cpp: In function 'void debug::init()':
malnarisc.cpp:22:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | void init() { for(int i = 0; i < n; ++i) { scanf("%d", a + i); } }
| ~~~~~^~~~~~~~~~~~~
malnarisc.cpp: In function 'int main()':
malnarisc.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
