oj.uz

답안 #409564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409564 2021-05-21T05:22:53 Z 534351 MalnaRISC (COI21_malnarisc) C++17
100 / 100
 12 ms 332 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 332 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 332 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 332 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 332 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 332 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 332 KB Output is correct