This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
}
}
cout << realAns.size() << endl;
for (auto x : realAns) cout << x.s << "ab"[x.f] << " ";
cout << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |