/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n;
string s;
int r = 0, g = 0, b = 0;
char cc[3] = {'R','G','Y'};
pair<int, string> solv(string t, int baskin){
vector<int> guzel;
vector<pair<int, char>> cop;
int m = t.size();
for(int i = 0; i < t.size(); ++i) {if(t[i] == cc[baskin]) guzel.pb(i); else cop.pb({i, t[i]});}
int num = 0;
if(t.length() % 2){
for(int i = 0; i < m; i += 2){
num += abs(guzel[i / 2] - i);
}
t = "";
for(int i = 0; i < m; ++i){
if(i%2) t += cop[i/2].second;
else t += cc[baskin];
}
}else{
string tt = t;
for(int i = 0; i < m; i += 2){
num += abs(guzel[i / 2] - i);
}
t = "";
for(int i = 0; i < m; ++i){
if(i%2) t += cop[i/2].second;
else t += cc[baskin];
}
int num1 = 0;
for(int i = 1; i < m; i += 2){
num1 += abs(guzel[i / 2] - i);
}
tt = "";
for(int i = 0; i < m; ++i){
if(i%2 == 0) tt += cop[i/2].second;
else tt += cc[baskin];
}
if(num > num1) swap(t, tt), swap(num, num1);
}
return {num, t};
}
void solve(){
cin >> n >> s;
for(int i = 0; i < n; ++i) r += s[i] == 'R', g += s[i] == 'G', b += s[i] == 'Y';
bool ok = 1;
int c =0 ;
if(r > (n+1)/2 || g > (n+1)/2 || b > (n+1)/2){
cout << -1;
return;
}
int ans =0 ;
while(ok){
ok = 0;
for(int i = n-1; i >= 1; --i){
int x = 0, y = 0, z = 0;
int last = i;
int lastf;
for(int j = i; j >= 0; --j){
x += s[j] == 'R';
y += s[j] == 'G';
z += s[j] == 'Y';
if(x > (i-j+2)/2) last = j, lastf = 0;
if(y > (i-j+2)/2) last = j, lastf = 1;
if(z > (i-j+2)/2) last = j, lastf = 2;
}
if(last == 0 || last >= i){
continue;
}
--last;
int cnt = 0;
auto p = solv(s.substr(last, i - last + 1), lastf);
for(int j = last; j <= i; ++j) s[j] = p.second[j - last];
ans += p.first;
if(p.first > 0){
ok = 1;
break;
}
}
if(!ok){
for(int i = 0; i < n-1; ++i){
int x = 0, y = 0, z = 0;
int last = i;
int lastf;
for(int j = i; j < n; ++j){
x += s[j] == 'R';
y += s[j] == 'G';
z += s[j] == 'Y';
if(x > (j-i+2)/2) last = j, lastf = 0;
if(y > (j-i+2)/2) last = j, lastf = 1;
if(z > (j-i+2)/2) last = j, lastf = 2;
}
if(last == n-1 || last == i){
continue;
}
++last;
int cnt = 0;
auto p = solv(s.substr(i, last - i + 1), lastf);
for(int j = i; j <= last; ++j) s[j] = p.second[j - i];
ans += p.first;
if(p.first > 0){
ok = 1;
break;
}
}
}
// cout << s << ' ';
// en;
// if(c>10) break;
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'std::pair<int, std::__cxx11::basic_string<char> > solv(std::string, int)':
joi2019_ho_t3.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0; i < t.size(); ++i) {if(t[i] == cc[baskin]) guzel.pb(i); else cop.pb({i, t[i]});}
| ~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:85:11: warning: unused variable 'cnt' [-Wunused-variable]
85 | int cnt = 0;
| ^~~
joi2019_ho_t3.cpp:111:13: warning: unused variable 'cnt' [-Wunused-variable]
111 | int cnt = 0;
| ^~~
joi2019_ho_t3.cpp:61:7: warning: unused variable 'c' [-Wunused-variable]
61 | int c =0 ;
| ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:131:15: warning: unused variable 'aa' [-Wunused-variable]
131 | int tt = 1, aa;
| ^~
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:112:55: warning: 'lastf' may be used uninitialized in this function [-Wmaybe-uninitialized]
112 | auto p = solv(s.substr(i, last - i + 1), lastf);
| ^
joi2019_ho_t3.cpp:86:56: warning: 'lastf' may be used uninitialized in this function [-Wmaybe-uninitialized]
86 | auto p = solv(s.substr(last, i - last + 1), lastf);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
