Submission #337029

#	Time	Username	Problem	Language	Result	Execution time	Memory
337029		thecodingwizard	Shift (POI11_prz)	C++11	0 / 100	170 ms	32328 KiB

prz

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13