#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define ordered_set(a) tree<a, null_type,less<a>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
int n;
string s, s2;
int mn=1e9;
void solve(int k, int r, int y, int g, int l){
if(y<0 || g<0 || r<0) return;
if(!l) s2[k-1]='R';
else if(l&1) s2[k-1]='Y';
else s2[k-1]='G';
if(k==n){
int sum=0;
pq_min(int) R, G, Y;
ordered_set(int) st;
rep(i,0,n){
if(s[i]=='R') R.push(i);
if(s[i]=='Y') Y.push(i);
if(s[i]=='G') G.push(i);
st.insert(i);
}
rep(i,0,n){
int b=0;
if(s2[i]=='R') b=R.top(), R.pop();
if(s2[i]=='Y') b=Y.top(), Y.pop();
if(s2[i]=='G') b=G.top(), G.pop();
sum+=st.order_of_key(b);
st.erase(b);
}
mn=min(mn,sum);
return;
}
if(!l) solve(k+1,r,y-1,g,1), solve(k+1,r,y,g-1,2);
else if(l&1) solve(k+1,r-1,y,g,0), solve(k+1,r,y,g-1,2);
else solve(k+1,r,y-1,g,1), solve(k+1,r-1,y,g,0);
}
int main(){
cin>>n>>s;
int r=0, g=0, y=0;
rep(i,0,n){
if(s[i]=='R') r++;
if(s[i]=='G') g++;
if(s[i]=='Y') y++;
}
s2=s;
solve(1,r-1,y,g,0);
solve(1,r,y-1,g,1);
solve(1,r,y,g-1,2);
if(n==1) mn=0;
if(mn<1e9) cout<<mn<<endl;
else cout<<-1<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
9 ms |
428 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
7 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
2 ms |
344 KB |
Output is correct |
| 12 |
Correct |
13 ms |
432 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
4 ms |
348 KB |
Output is correct |
| 15 |
Correct |
2 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
9 ms |
428 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
7 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
2 ms |
344 KB |
Output is correct |
| 12 |
Correct |
13 ms |
432 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
4 ms |
348 KB |
Output is correct |
| 15 |
Correct |
2 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Execution timed out |
1076 ms |
348 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
344 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
9 ms |
428 KB |
Output is correct |
| 7 |
Correct |
2 ms |
344 KB |
Output is correct |
| 8 |
Correct |
7 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
2 ms |
344 KB |
Output is correct |
| 12 |
Correct |
13 ms |
432 KB |
Output is correct |
| 13 |
Correct |
1 ms |
344 KB |
Output is correct |
| 14 |
Correct |
4 ms |
348 KB |
Output is correct |
| 15 |
Correct |
2 ms |
344 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Execution timed out |
1076 ms |
348 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
