Submission #330958

#TimeUsernameProblemLanguageResultExecution timeMemory
330958MetBShift (POI11_prz)C++14
0 / 100
184 ms11336 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...