Submission #22995030

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

/* // Ordered Set
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define os_find(k) find_by_order(k)
#define os_order(k) order_of_key(k)
*/

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
#define f0(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>b;i--)
#define f3(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
// or add ll at the end for long long
#define cntleadz(x) __builtin_clz(x)
#define cnttrailz(x) __builtin_ctz(x)
#define cntpop(x) __builtin_popcount(x)
#define binparity(x) __builtin_parity(x)
#define pb push_back
#define pii pair<int,int>
#define int long long
#define fi first
#define se second
#define mod 1000000007
// #define mod 998244353
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define make_graph(k) int x,y; f0(i,0,k){cin>>x>>y; adj[x].pb(y); adj[y].pb(x);}
#define test int t;cin>>t;while(t--)

ll binExp(ll x,ll n,ll m)
{
    ll res=1;
    while(n)
    {
        if(n&1) res=(res*x)%m;
        x=(x*x)%m;
        n>>=1;
    }
    return res;
}

ll modInv(ll i, ll m) {return binExp(i,m-2,m);}
ll add(ll a, ll b) {ll res = a+b; if(res >= mod) res -= mod; if(res < 0) res += mod; return res;}
ll mul(ll a, ll b) {ll res = (a)*(b); res %= mod; if(res < 0) res += mod; return res;}
// ll fact[1000001];
// ll ncr(int n,int r) {return (n>=r?(fact[n]*modInv(fact[r],mod))%mod*modInv(fact[n-r],mod)%mod:0);}

// https://codeforces.com/contest/558/problem/E
// Do this question via the current method as
// well as SegTree with Lazy propagation



void solve()
{
    int n;
    cin>>n;

    char col;
    int x;
    vector<int> r,g,b;
    f0(i,0,2*n)
    {
        cin>>x>>col;
        if(col == 'R') r.pb(x);
        else if(col == 'G') g.pb(x);
        else b.pb(x);
    }

    sort(all(r));
    sort(all(g));
    sort(all(b));

    if(r.size()%2 == 0 && g.size()%2 == 0 && b.size()%2 == 0)
    {
        cout<<"0\n";
        return;
    }

    if(r.size()%2==0)
    {
        swap(b,r);
    }
    else if(g.size()%2==0)
    {
        swap(g,b);
    }

    // now r and g are the odd ones
    // cout<<r.size()<<' '<<g.size()<<' '<<b.size()<<'\n';

    int ans = LLONG_MAX;

    for(int x : r)
    {
        auto it = lower_bound(all(g),x);
        if(it != g.end())
        {
            ans = min(ans, abs(x-*it));
        }
        if(it != g.begin())
        {
            ans = min(ans, abs(x-*prev(it)));
        }
    }

    int mnR[b.size()];
    int mnG[b.size()];

    f0(i,0,b.size())
    {
        auto it = lower_bound(all(r),b[i]);
        int mn = LLONG_MAX;
        if(it != r.end())
        {
            mn = min(mn, abs(b[i]-*it));
        }
        if(it != r.begin())
        {
            mn = min(mn, abs(b[i]-*prev(it)));
        }
        mnR[i] = mn;
        mn = LLONG_MAX;
        it = lower_bound(all(g),b[i]);
        if(it != g.end())
        {
            mn = min(mn, abs(b[i]-*it));
        }
        if(it != g.begin())
        {
            mn = min(mn, abs(b[i]-*prev(it)));
        }
        mnG[i] = mn;
    }

    f0(i,1,b.size())
    {
        ans = min(ans, mnR[i]+mnG[i-1]);
        ans = min(ans, mnG[i]+mnR[i-1]);
        mnG[i] = min(mnG[i], mnG[i-1]);
        mnR[i] = min(mnR[i], mnR[i-1]);
    }
    cout<<ans<<'\n';
}

signed main()
{
    fast

    clock_t start,end;
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    start = clock();

    int tc;
    tc = 1;
    // cin>>tc;
    f1(i,1,tc)
        solve();

    end = clock();
    double time_taken = double(end-start) / double(CLOCKS_PER_SEC);
    // cout<<time_taken<<" sec";
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:23:32: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 | #define f0(i,a,b) for(int i=a;i<b;i++)
......
  124 |     f0(i,0,b.size())
      |        ~~~~~~~~~~~~             
./Main.cpp:124:5: note: in expansion of macro ‘f0’
  124 |     f0(i,0,b.size())
      |     ^~
./Main.cpp:23:32: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 | #define f0(i,a,b) for(int i=a;i<b;i++)
......
  150 |     f0(i,1,b.size())
      |        ~~~~~~~~~~~~             
./Main.cpp:150:5: note: in expansion of macro ‘f0’
  150 |     f0(i,1,b.size())
      |     ^~
./Main.cpp: In function ‘int main()’:
./Main.cpp:178:12: warning: unused variable ‘time_taken’ [-Wunused-variable]
  178 |     double time_taken = double(end-start) / double(CLOCKS_PER_SEC);
      |            ^~~~~~~~~~

Judge Result