Submission #305840

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
305840	2020-09-24T02:29:22 Z	caoash	Shift (POI11_prz)	C++14	100 / 100	281 ms	40640 KB

#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[i]) ++cnt;
        }
    }
    if (n % 2 == 1 && cnt % 2 == 1) {
        cout << "NIE DA SIE" << '\n';
        return 0;
    }
    int last = 2;
    vector<pair<char, int>> moves;
    auto dist = [&] (int i, int j) {
        if (i > j) {
            return i - j;
        }
        else {
            return (n - j) + i;
        }
    };
    auto swap3 = [&] (int i) {
        // dbg(i);
        if (last != i) {
            int req = dist(last, i);
            // dbg(last, i, req);
            moves.pb(mp('a', req));
            last = i;
        }
        moves.pb(mp('b', 1));
        int prev = (i - 1 < 0 ? n - 1 : i - 1);
        int two = (i - 2 < 0 ? n + i - 2 : i - 2);
        // dbg(i, prev, two);
        swap(a[i], a[two]);
        swap(a[i], a[prev]);
    };
    auto find = [&] (int v) {
        for (int j = 0; j < n; j++) {
            if (a[j] == v) {
                return j;
            }
        }
        return -1;
    };
    for (int i = 2; i <= n; i++) {
        int pos = find(i);
        if (a[(pos - 1 + n) % n] + 1 == i) {
            continue;
        }
        if (i <= n - 2) {
            int curr = pos;
            while (a[curr] != a[(curr - 1 + n) % n] + 1 && a[curr] != a[(curr - 2 + n) % n] + 1) {
                swap3(curr);
                curr = (curr - 2 + n) % n;
            }
            if (a[curr] == a[(curr - 2 + n) % n] + 1) {
                swap3((curr + 1) % n);
                swap3((curr + 1) % n);
            }
        }
        else {
            int curr = pos;
            while (a[curr] != a[(curr - 1 + n) % n] + 1) {
                swap3(curr);
                curr = (curr - 2 + n) % n;
            }
        }
        // dbg(a);
    }
    // dbg(a);
    // dbg(moves);
    // dbg(last);
    // dbg(a);
    int fst = find(1);
    if ((last - 2 + n) % n != fst) {
        moves.pb(mp('a', dist((last - 2 + n) % n, fst))); 
    }
    reverse(all(moves));
    vector<pair<char, int>> ret;
    while (!moves.empty()) {
        pair<char, int> fr = moves.back();
        if (ret.empty()) {
            ret.pb(fr);
        }
        else {
            if (fr.f == ret.back().f) {
                ret.back().s += fr.s;
            }
            else {
                ret.pb(fr);
            }
        }
        moves.pop_back();
    }
    cout << sz(ret) << '\n';
    for (auto x : ret) {
        cout << x.s << x.f << " ";
    }
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 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	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	17632 KB	Output is correct
2	Correct	99 ms	17636 KB	Output is correct
3	Correct	99 ms	17760 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	18924 KB	Output is correct
2	Correct	120 ms	19040 KB	Output is correct
3	Correct	124 ms	19040 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	20444 KB	Output is correct
2	Correct	158 ms	20564 KB	Output is correct
3	Correct	281 ms	40640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct

Submission #305840

Compilation message