제출 #1130117

#제출 시각아이디문제언어결과실행 시간메모리
1130117am_aadvikGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
20 / 100
4 ms328 KiB
#include <iostream>
#include<vector>
#define int long long
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;
				}
			for (int j = val; j > i; --j)
				swap(s[j], s[j - 1]), ans++;
		}
	return ans;
}

int res = 1e17, 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 <= 20) {
		string c = "";
		for (int i = 0; i < 3; ++i) {
			c = "RGY"[i]; sol("RGY"[i], c, n);
		}
		cout << (res == 1e17 ? -1 : res);
		return 0;
	}


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

	int ans = 1e17;
	if (g >= r) ans = min(ans, cnt(s, a2));
	if (r >= g) ans = min(ans, cnt(s, a1));
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...