Submission #337047

#	Time	Username	Problem	Language	Result	Execution time	Memory
337047		thecodingwizard	Shift (POI11_prz)	C++11	0 / 100	157 ms	30912 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();

    //cout << "Solving " << x << ": " << endl;
    while (tgtIdx != curIdx) {
        int destIdx = max(curIdx - 2, tgtIdx);
        ans.pb(mp(1, n-destIdx));
        //cout << ans.back().s << "b" << endl;
        if (destIdx == curIdx - 2) {
            ans.pb(mp(0, 1));
            //cout << ans.back().s << "a" << endl;
            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));
            //cout << ans.back().s << "a" << endl;
            int tmp = A[destIdx];
            A[destIdx] = A[curIdx];
            A[curIdx] = A[curIdx+1];
            A[curIdx+1] = tmp;
        }
        ans.pb(mp(1, destIdx));
        //cout << ans.back().s << "b" << endl;
        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();
            ans.pb(mp(1, n-1));
        } 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.f == 1) {
                    cur.s %= n;
                }
                if (cur.f == 0) {
                    cur.s %= 3;
                }
                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