Submission #330956

#	Time	Username	Problem	Language	Result	Execution time	Memory
330956		MetB	Shift (POI11_prz)	C++14	0 / 100	185 ms	11336 KiB

prz

#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 << ' ';
	}
	cout << endl;

	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++) {
      |                  ~~^~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13