Submission #409564

#	Time	Username	Problem	Language	Result	Execution time	Memory
409564		534351	MalnaRISC (COI21_malnarisc)	C++17	100 / 100	12 ms	332 KiB

malnarisc

#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;
}

• 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