oj.uz

Submission #337029

# Submission time Handle Problem Language Result Execution time Memory
337029 2020-12-18T02:00:17 Z thecodingwizard Shift (POI11_prz) C++11
0 / 100
 170 ms 32328 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

int n; 
vector<ii> ans;
vector<int> A;

void solve(int x) {
    int tgtIdx = x-1;
    int curIdx = find(all(A), x)-A.begin();

    while (tgtIdx != curIdx) {
        int destIdx = max(curIdx - 2, tgtIdx);
        ans.pb(mp(1, n-destIdx));
        if (destIdx == curIdx - 2) {
            ans.pb(mp(0, 1));
            int tmp = A[curIdx];
            A[curIdx] = A[destIdx+1];
            A[destIdx+1] = A[destIdx];
            A[destIdx] = tmp;
        } else {
            assert(destIdx == curIdx - 1);
            ans.pb(mp(0, 2));
            int tmp = A[destIdx];
            A[destIdx] = A[curIdx];
            A[curIdx] = A[curIdx+1];
            A[curIdx+1] = tmp;
        }
        ans.pb(mp(1, n-((tgtIdx+n)-curIdx)));
        curIdx = destIdx;
    }
}

void process() {
    FOR(i, 1, n-1) {
        solve(i);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    F0R(i, n) {
        int x; cin >> x; A.pb(x);
    }

    process();

    if (A.back() != n) {
        if (n % 2 == 0) {
            ans.pb(mp(1, 1));
            A.insert(A.begin(), A.back());
            A.pop_back();
            process();
        } else {
            cout << "NIE DA SIE" << endl;
            return 0;
        }
    }

    vector<ii> realAns;
    ii cur = mp(-1, -1);
    for (auto x : ans) {
        if (cur.f == -1) cur = x;
        else {
            if (cur.f == x.f) {
                cur.s += x.s;
            } else {
                if (cur.s >= n) assert(cur.f == 1);
                //if (cur.f == 0) assert(cur.s <= 2);
                cur.s %= n;
                if (cur.s == 0) {
                    if (!realAns.empty()) {
                        cur = realAns.back();
                        assert(cur.f == x.f);
                        realAns.pop_back();
                        cur.s += x.s;
                    } else {
                        cur = x;
                    }
                } else {
                    realAns.pb(cur);
                    cur = x;
                }
            }
        }
    }
    cur.s %= n;
    if (cur.s != 0) realAns.pb(cur);

    cout << realAns.size() << endl;
    for (auto x : realAns) cout << x.s << "ab"[x.f] << " ";
    cout << endl;

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Liczby nie zostaly posortowane
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 748 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2276 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 20192 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 27968 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 32328 KB Liczby nie zostaly posortowane
2 Halted 0 ms 0 KB -