Submission #337054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337054	2020-12-18T04:23:58 Z	thecodingwizard	Shift (POI11_prz)	C++11	100 / 100	310 ms	61980 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();

    //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();
        } 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;
                }
            }
        }
    }
    if (cur.f != -1) {
        cur.s %= n;
        if (cur.s != 0) realAns.pb(cur);
    }

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

    return 0;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	3 ms	748 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	2276 KB	Output is correct
2	Correct	10 ms	2276 KB	Output is correct
3	Correct	10 ms	2276 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	20192 KB	Output is correct
2	Correct	101 ms	20392 KB	Output is correct
3	Correct	98 ms	20064 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	130 ms	26944 KB	Output is correct
2	Correct	133 ms	27200 KB	Output is correct
3	Correct	125 ms	26432 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	31040 KB	Output is correct
2	Correct	155 ms	31168 KB	Output is correct
3	Correct	310 ms	61980 KB	Output is correct
4	Correct	2 ms	364 KB	Output is correct
5	Correct	15 ms	8676 KB	Output is correct

Submission #337054

Compilation message