Submission #1322523

#TimeUsernameProblemLanguageResultExecution timeMemory
1322523Roumak77Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
1094 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {

    ll n;
    cin >> n;
    
    string s;
    cin >> s;
    
    ll r = 0, g = 0, y = 0;
    multiset<ll> R;
    multiset<ll> G;
    multiset<ll> Y;
    for(ll j = 0; j < n; j++){
        char i = s[j];
        if(i == 'R'){
            r++;
            R.insert(j);
        }else if(i == 'G'){
            g++;
            G.insert(j);
        }else if(i == 'Y'){
            y++;
            Y.insert(j);
        }
    }
    
    if(max(max(r, g), y) > (n + 1)/2){
        cout << -1 << endl;
        return 0;
    }
    
    string s1 = "";
    string s2 = "";
    
    for(ll i = 0; i < n; i++){
        if(i%2 == 0){
            s1 += "R";
            s2 += "G";
        }else{
            s1 += "G";
            s2 += "R";
        }
    }
    
    o_set<ll> o1;
    o1.insert(999999);
    ll ans = 1e17;
    if(r == (n + 1)/2){
        ll c1 = 0;
        for(ll i = 0; i < n; i++){
            if(i%2 == 0){
                auto t = *R.begin();
                R.erase(R.begin());
                ll minus = o1.order_of_key(t);
                c1 += t - minus;
                o1.insert(t);
            }else{
                auto t = *G.begin();
                G.erase(G.begin());
                ll minus = o1.order_of_key(t);
                c1 += t - minus;
                o1.insert(t);
            }
        }
        ans = min(ans, c1);
    }
    
    o_set<ll> o2;
    o2.insert(999999);
    
    if(g == (n + 1)/2){
        for(ll j = 0; j < n; j++){
            char i = s[j];
            if(i == 'R'){
               
                R.insert(j);
            }else if(i == 'G'){
                G.insert(j);
            }else if(i == 'Y'){
                Y.insert(j);
            }
        }
        ll c1 = 0;
        for(ll i = 0; i < n; i++){
            if(i%2 == 1){
                auto t = *R.begin();
                R.erase(R.begin());
                ll minus = o2.order_of_key(t);
                c1 += t - minus;
                o2.insert(t);
            }else{
                auto t = *G.begin();
                G.erase(G.begin());
                ll minus = o2.order_of_key(t);
                c1 += t - minus;
                o2.insert(t);
            }
        }
        ans = min(ans, c1);
    }
    cout << ans << endl;
    
    
    


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...