#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
mt19937 rng(42);
template<class T>
T randomize(T mod)
{
return uniform_int_distribution<T>(0, mod - 1)(rng);
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N;
vector<vpi> ans;
vector<vpi> comb(vector<vpi> l, vector<vpi> r)
{
if (SZ(l) < SZ(r)) swap(l, r);
FOR(i, 0, SZ(r))
{
l[i].insert(l[i].end(), ALL(r[i]));
}
return l;
}
vector<vpi> genmerge(int L, int R, bool dir)
{
cerr << "GENMERGE " << L << ' ' << R << endl;
if (L == R)
{
return vector<vpi>();
}
vector<vpi> res; res.PB(vpi());
int M = (1 << (31 - __builtin_clz(R - L)));
FOR(i, L, R + 1 - M)
{
pii p = {i, i + M};
if (dir) swap(p.fi, p.se);
res.back().PB(p);
}
auto lt = genmerge(L, L + M - 1, dir);
auto rt = genmerge(L + M, R, dir);
lt = comb(lt, rt);
res.insert(res.end(), ALL(lt));
return res;
}
//sorts a random L...R
vector<vpi> gensort(int L, int R, bool dir)
{
// cerr << "GENSORT " << L << ' ' << R << endl;
if (L == R)
{
return vector<vpi>();
}
int mid = (L + R) >> 1;
auto lt = gensort(L, mid, !dir);
auto rt = gensort(mid + 1, R, dir);
lt = comb(lt, rt);
auto cd = genmerge(L, R, dir);
lt.insert(lt.end(), ALL(cd));
return lt;
}
int32_t main()
{
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N;
vi arr(N);
iota(ALL(arr), 0);
FOR(i, 1, N)
{
swap(arr[i], arr[randomize(i + 1)]);
}
// for (int i = 1; i < 4 * N; i += i)
// {
// for (int j = i; j; j >>= 1)
// {
// ans.PB(vpi());
// for (int k = 0; k < N; k += 2 * j)
// {
// FOR(m, 0, j)
// {
// if (k + m + j < N)
// {
// pii p = {k + m, k + m + j};
// if (k / (2 * i) % 2)
// {
// swap(p.fi, p.se);
// }
// ans.back().PB(p);
// }
// //j, j + i.
// }
// }
// if (ans.back().empty())
// {
// ans.pop_back();
// }
// }
// }
ans = gensort(0, N - 1, false);
cout << SZ(ans) << '\n';
for (vpi v : ans)
{
for (pii p : v)
{
if (arr[p.fi] > arr[p.se])
{
swap(arr[p.fi], arr[p.se]);
}
cout << "CMPSWP R" << p.fi + 1 << " R" << p.se + 1 << ' ';
}
cout << '\n';
}
// FOR(i, 0, N)
// {
// cerr << arr[i] << ' ';
// }
// cerr << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
332 KB |
Output is correct |
