Submission #22996626

---

Source Code Expand

//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word
//ctrl+end - to break infinite loop in sublime text
 
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
using namespace std; 
#define Fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)
#define ll long long int
#define fo(i, a, b) for (long long int i = a; i <= b; i++)
#define w(t)  \
    int t;    \
    cin >> t; \
    while (t--)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vl vector<long long int>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long int>>
#define mii map<int, int>
#define umii unordered_map<int, int>
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define newl cout<<"\n"
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll inf = 1e9+7;
const ll mod = 998244353 ;
#define MAX 200005 

void call_priyanshu(){
    Fio;
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

ll mini(ll a,ll b){
    if(a>=b)return b;
    return a;
}
 
ll maxi(ll a,ll b){
    if(a>=b)return a;
    return b;
}

ll calc(vl &A,vl &B,ll n,ll m){
    ll ans=1e18;
    fo(i,0,n-1){
        auto b = lower_bound(all(B),A[i]);
        if(b!=B.end())ans = mini(ans,abs(*b-A[i]));
        auto bb = upper_bound(all(B),A[i]);
        if(bb!=B.end())ans = mini(ans,abs(*bb-A[i]));
    }
    fo(i,0,m-1){
        auto b = lower_bound(all(A),B[i]);
        if(b!=A.end())ans = mini(ans,abs(*b-B[i]));
        auto bb = upper_bound(all(A),B[i]);
        if(bb!=A.end())ans = mini(ans,abs(*bb-B[i]));
    }
    return ans;
}

ll calc2(vl &A,vl &B,vl &C,ll n,ll m,ll nn){
    ll a1 = calc(A,B,n,m);
    ll a2 = calc(A,C,n,nn);
    return (a1+a2);
}

void solve(){
    //write your code here
    ll n;
    cin>>n;
    vl B,R,G;
    fo(i,0,2*n-1){
        ll v;
        char c;
        cin>>v>>c;
        if(c=='B'){
            B.pb(v);
        }
        if(c=='R'){
            R.pb(v);
        }
        if(c=='G'){
            G.pb(v);
        }
    }
    sort(all(B));
    sort(all(R));
    sort(all(G));
    ll b = B.size(),r=R.size(),g = G.size();
    if(b%2==0 && r%2==0 && g%2==0){
        cout<<"0";
        return;
    }
    ll ans = 0,ans2 = 0;
    if(b%2==0){
        ans = calc(R,G,r,g);
        if(b!=0){
            ans2 = calc2(B,R,G,b,r,g);
            ans = mini(ans,ans2);
        }
    }
    if(r%2==0){
        ans = calc(B,G,b,g);
        if(r!=0){
            ans2 = calc2(R,B,G,r,b,g);
            ans = mini(ans,ans2);
        }   
    }
    if(g%2==0){
        ans = calc(B,R,b,r);
        if(g!=0){
            ans2 = calc2(G,B,R,g,b,r);
            ans = mini(ans,ans2);
        }
    }
    cout<<ans;
}


int main(){
    call_priyanshu();
    // w(T){
        solve();
    // }
    return 0;
}

Submission Info

Judge Result