#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) x.size()
#define pb push_back
#define F first
#define S second
#define nl '\n'
const int inf = 1e12;
bool ch( string s )
{
for( int i = 1; i < sz(s); ++i )
if( s[i] == s[i - 1] )
return false;
return true;
}
void solve()
{
int n;
string s;
cin >>n >>s;
int x, y, z;
x = y = z = 0;
vector< int >r, g;
for( int i = 0; i < n; ++i )
{
if( s[i] == 'R' )
{
r.pb( i );
++x;
}
if( s[i] == 'G' )
{
g.pb( i );
++y;
}
if( s[i] == 'Y' )
++z;
}
if( x - 1 > y + z || y - 1 > x + z || z - 1 > x + y )
{
cout <<-1 <<nl;
return;
}
if( y + x == n )
{
if( y > x )
{
swap(x, y);
swap(r, g);
for( int i = 0; i < n; ++i )
swap(pr[i], pg[i]);
}
int ans = 0;
if( x > y )
{
int pos = 1;
for( int i: g )
{
ans += abs(pos - i);
pos += 2;
}
}
else
{
int cnt1 = 0, cnt2 = 0, pos = 0;
for( int i: r )
{
cnt1 += abs(i - pos);
pos += 2;
}
pos = 0;
for( int i: g )
{
cnt2 += abs(i - pos);
pos += 2;
}
ans = min(cnt1, cnt2);
}
cout <<ans <<nl;
return;
}
else
{
int ans = inf;
map<string, int>mp;
queue< string >q;
mp[s] = 0;
q.push(s);
while( !q.empty() )
{
string v = q.front();
q.pop();
if( ch(v) )
{
ans = min(ans, (int)mp[v]);
continue;
}
for( int i = 1; i < n; ++i )
{
string v1 = v;
swap(v1[i], v1[i - 1]);
if( !mp.count(v1) )
{
mp[v1] = mp[v] + 1;
q.push(v1);
}
}
}
cout <<ans;
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T = 1;
cin >>T;
// while( T-- )
solve();
}
Compilation message
joi2019_ho_t3.cpp: In function 'bool ch(std::string)':
joi2019_ho_t3.cpp:16:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for( int i = 1; i < sz(s); ++i )
| ^
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:57:10: error: 'pr' was not declared in this scope; did you mean 'r'?
57 | swap(pr[i], pg[i]);
| ^~
| r
joi2019_ho_t3.cpp:57:17: error: 'pg' was not declared in this scope; did you mean 'g'?
57 | swap(pr[i], pg[i]);
| ^~
| g
