//#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
//#pragma GCC target("avx2") //Enable AVX
#include<bits/stdc++.h>
using namespace std;
#define all(a) begin(a),end(a)
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
void clr(auto &a,int n){
a.clear();
a.resize(n);
}
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
input>>x.F>>x.S;
return input;
}
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
for(auto& i:x)
input>>i;
return input;
}
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
for(auto& i:x)
output<<i<<' ';
return output;
}
template<typename T>
vector<pair<T,int>> getvec(int n){
vector<pair<T,int>>a(n);
for(int i=0;i<a.size();i++){
cin>>a[i].F;
a[i].S=i;
}
return a;
}
const int mod=1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int mul(int a,int b){
return ((a)*1ll*(b))%mod;
}
void add(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
int sub(int a,int b){
a-=b;
if(a<0){
a+=mod;
}
return a;
}
int powz(int a,int b){
int res=1;
while(b){
if(b&1){
res=mul(res,a);
}
b/=2;
a=mul(a,a);
}
return res;
}
const int N=405;
int dp[2][405][405][3];
vector<int>adj[3];
struct ordered_set {
int sz = 0, bit[N];
int size() {
return sz;
}
void update(int k, int x) {
k++;
while (k < N) {
bit[k] += x;
k += k & -k;
}
sz += x;
}
int find_by_order(int k) {
int ans = 0, sum = 0;
for (int j = 17; j >= 0; --j) {
ans += 1 << j;
if (ans < N && sum + bit[ans] < k) {
sum += bit[ans];
} else {
ans -= 1 << j;
}
}
return ans + 1;
}
int order_of_key(int k) {
k++;
int ans = 0;
while (k >= 1) {
ans += bit[k];
k -= k & -k;
}
return ans - 1;
}
}st[405][405];
void solve(){
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i<s.length();i++){
if(s[i]=='R'){
adj[0].pb(i);
}
else if(s[i]=='G'){
adj[1].pb(i);
}
else{
adj[2].pb(i);
}
}
int mx=max({(int)adj[0].size(),(int)adj[1].size(),(int)adj[2].size()});
if(mx*2>n){
cout<<-1;
return;
}
for(int i=0;i<=adj[0].size();i++){
for(int j=0;j<=adj[1].size();j++){
for(int k=0;k<n;k++){
st[i][j].update(k,1);
}
for(int k=0;k<i;k++){
st[i][j].update(adj[0][k],-1);
}
for(int k=0;k<j;k++){
st[i][j].update(adj[1][k],-1);
}
}
}
for(int i=0;i<2;i++){
for(int j=0;j<=adj[0].size();j++){
for(int k=0;k<=adj[1].size();k++){
for(int l=0;l<3;l++){
dp[i][j][k][l]=1e9;
}
}
}
}
dp[0][0][0][0]=0;
dp[0][0][0][1]=0;
dp[0][0][0][2]=0;
for(int i=0;i<n;i++){
for(int j=0;j<=min(i,(int)adj[0].size());j++){
for(int k=0;k<=min(i,(int)adj[1].size());k++){
if(i-(j+k)<0){
continue;
}
for(int l=0;l<3;l++){
if(dp[0][j][k][l]==1e9){
continue;
}
for(int put=0;put<3;put++){
if(put==l){
continue;
}
if(put==0){
if(j+1>adj[0].size()){
continue;
}
int fnd=st[j][k].order_of_key(adj[0][j]);
dp[1][j+1][k][0]=min(dp[1][j+1][k][0],dp[0][j][k][l]+fnd);
}
else if(put==1){
if(k+1>adj[1].size()){
continue;
}
int fnd=st[j][k].order_of_key(adj[1][k]);
dp[1][j][k+1][1]=min(dp[1][j][k+1][1],dp[0][j][k][l]+fnd);
}
else{
if((i-(j+k)+1)>adj[2].size()){
continue;
}
int fnd=st[j][k].order_of_key(adj[2][i-(j+k)]);
dp[1][j][k][2]=min(dp[1][j][k][2],dp[0][j][k][l]+fnd);
}
}
}
}
}
for(int j=0;j<=adj[0].size();j++){
for(int k=0;k<=adj[1].size();k++){
if(i-(j+k)<0){
continue;
}
if(i+1-(j+k)>adj[2].size()){
continue;
}
st[j][k].update(adj[2][i-(j+k)],-1);
}
}
for(int j=0;j<=min(i+1,(int)adj[0].size());j++){
for(int k=0;k<=min(i+1,(int)adj[1].size());k++){
for(int l=0;l<3;l++){
dp[0][j][k][l]=dp[1][j][k][l];
dp[1][j][k][l]=1e9;
}
}
}
}
int ans=1e9;
ans=min(ans,dp[0][adj[0].size()][adj[1].size()][0]);
ans=min(ans,dp[0][adj[0].size()][adj[1].size()][1]);
ans=min(ans,dp[0][adj[0].size()][adj[1].size()][2]);
if(ans==1e9){
ans=-1;
}
cout<<ans;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc=1;
//cin>>tc;
for(int _=0;_<tc;_++){
// cout<<"Case #"<<_+1<<": ";
solve();
if(_!=tc-1){
cout<<'\n';
}
}
}
Compilation message
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.length();i++){
~^~~~~~~~~~~
joi2019_ho_t3.cpp:155:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<=adj[0].size();i++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<=adj[1].size();j++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<=adj[0].size();j++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:170:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<=adj[1].size();k++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:195:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j+1>adj[0].size()){
~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:202:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(k+1>adj[1].size()){
~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:209:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if((i-(j+k)+1)>adj[2].size()){
~~~~~~~~~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:219:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<=adj[0].size();j++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:220:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<=adj[1].size();k++){
~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:224:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i+1-(j+k)>adj[2].size()){
~~~~~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
260968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
260968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
130 ms |
260984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
128 ms |
260968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
