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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const int N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
struct cyclic_array {
vector <int> v;
int shift, n;
cyclic_array(int n)
: v (vector <int> (n)), shift (0), n (n) {}
void make_b() {
shift = shift ? shift - 1 : n - 1;
}
void make_inv() {
shift = (shift == n - 1) ? 0 : shift + 1;
}
void make_a() {
int& a = v[shift % n];
int& b = v[(shift + 1) % n];
int& c = v[(shift + 2) % n];
swap(b, c), swap(a, b);
}
int& operator[] (int x) {
return v[(x + shift) % n];
}
};
vector <pair<int, char>> s;
int n;
void add_a(cyclic_array& v) {
v.make_a();
if (!s.empty() && s.back().second == 'a') s.back().first++;
else s.push_back({1, 'a'});
if (s.back().first == n) s.pop_back();
}
void add_b(cyclic_array& v) {
v.make_b();
if (!s.empty() && s.back().second == 'b') s.back().first++;
else s.push_back({1, 'b'});
if (s.back().first == n) s.pop_back();
}
void add_inv(cyclic_array& v) {
v.make_inv();
if (!s.empty() && s.back().second == 'b') s.back().first = (s.back().first + n - 1) % n;
else s.push_back({n - 1, 'b'});
if (s.back().first == 0) s.pop_back();
}
bool check (vector <int> a) {
for (int i = 0; i < s.size (); i++) {
for (int j = 0; j < s[i].first; j++) {
if (s[i].second == 'b') {
int x = a.back ();
for (int i = a.size () - 2; i >= 0; i--)
a[i+1] = a[i];
a[0] = x;
}
else {
int x = a[0];
a[0] = a[2];
a[2] = a[1];
a[1] = x;
}
}
for (int i = 0; i < n; i++) {
//cout << a[i] << ' ';
}
//cout << endl;
}
for (int i = 0; i < n; i++) {
if (a[i] != i + 1) return false;
}
return true;
}
bool solve (vector <int> d) {
s.clear ();
//cin >> n;
n = d.size ();
cyclic_array v (n);
vector <int> a (n);
for (int i = 0; i < n; i++) {
//cin >> v[i];
v[i] = d[i];
a[i] = v[i];
}
for (int i = 2; i <= n; i++) {
while (v[2] != i) add_b(v);
while (v[0] != i - 1 && v[1] != i - 1) {
add_a(v), add_b(v), add_b(v);
}
if (v[0] == i - 1) {
if (i >= n - 1) {
if (n % 2 == 0) {
while (v[1] != i - 1) {
add_a(v), add_b(v), add_b(v);
}
} else {
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) {
if (a[j] > a[i]) cnt ^= 1;
}
if (!cnt) {
cout << "WRONG\n";
for (int i = 0; i < n; i++) {
cout << a[i] << ' ' << v[i] << endl;
}
cout << "=============" << endl;
}
//cout << "CORRECT\n";
cout << "NIE DA SIE\n";
return 0;
}
} else {
add_inv(v), add_a(v), add_a(v);
}
}
}
while (v[0] != 1) add_b(v);
//if (!check (a)) cout << "WRONG\n";
//else cout << "CORRECT\n";
assert (n * n >= s.size ());
cout << s.size () << endl;
for (auto a : s) {
cout << a.first << a.second << ' ';
}
return 0;
}
int main () {
cin >> n;
vector <int> v (n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
solve (v);
/*int t;
cin >> n >> t;
vector <int> v (n);
while (t--) {
vector <int> x (n);
for (int i = 0; i < n; i++) {
int pos = rand () % n;
while (x[pos]) pos = rand () % n;
x[pos] = 1;
v[pos] = i + 1;
}
for (int i = 0; i < n; i++) {
cout << v[i] << ' ';
}
solve(v);
}*/
}
Compilation message (stderr)
prz.cpp: In function 'bool check(std::vector<int>)':
prz.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i < s.size (); i++) {
| ~~^~~~~~~~~~~
# | 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... |