Submission #1130115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130115		am_aadvik	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	5 ms	328 KiB

joi2019_ho_t3

#include <iostream>
#include<vector>
using namespace std;

string alt(int n, bool c) {
	string ans = "";
	while (n--)
		ans += "RG"[c], c ^= 1;
	return ans;
}

int cnt(string s, string t) { //s->t
	int n = s.length(), ans = 0;
	for (int i = 0; i < n; ++i)
		if (s[i] != t[i]) {
			int val = 0;
			for (int j = i + 1; j < n; ++j)
				if (s[j] == t[i]) {
					val = j; break;
				}
			ans += val - i, swap(s[i], s[val]);
		}
	return ans;
}

int res = 1e8, gc = 0, rc = 0, yc = 0;
string s;
void sol(char p, string& c, int n) {
	if (c.length() == n) {
		int r = 0, y = 0, g = 0;
		for (int i = 0; i < n; ++i)
			if (c[i] == 'R') r++;
			else if (c[i] == 'G') g++;
			else y++;
		if ((r != rc) || (y != yc) || (g != gc))
			return;
		res = min(res, cnt(s, c));
		return;
	}

	for (int i = 0; i < 3; ++i)
		if ("RGY"[i] != p) {
			c += "RGY"[i];
			sol("RGY"[i], c, n);
			c.pop_back();
		}
}

int32_t main()
{
	int n, r = 0, g = 0; cin >> n;
	string a1 = alt(n, 0), a2 = alt(n, 1); cin >> s;
	for (int i = 0; i < n; ++i)
		if (s[i] == 'R') r++;
		else if (s[i] == 'G') g++;
		else yc++;
	gc = g, rc = r;

	if (n <= 15) {
		string c = "";
		for (int i = 0; i < 3; ++i)
			c = "RGY"[i], sol("RGY"[i], c, n);
		cout << (res == 1e8 ? -1 : res);
		return 0;
	}


	if (abs(g - r) > 1) { cout << -1; return 0; }

	int ans = 1e8;
	if (g >= r) ans = min(ans, cnt(s, a2));
	if (r >= g) ans = min(ans, cnt(s, a1));
	cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25