HackerEarth Coins problem solution

In this HackerEarth Coins problem solution, There are N bags and each bag contains some coin(s). Your task is to select an integer X and remove all the bags in which the number of coins is equal to X. Divide the remaining bags into two non-empty groups such that:

1. The number of coin(s) in each bag of the first group is strictly smaller than X.
2. The number of coin(s) in each bag of the second group is strictly larger than X.
3. The total number of coins of one group is equal to the other.

HackerEarth Coins problem solution.

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define le length()
#define sz size()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;

// Template End
const int MAX = 1e5 + 5;
ll pre[MAX], suf[MAX];
int A[MAX];
VII v;

int main(int argc, char* argv[]) {
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    ios::sync_with_stdio(false);
    int n, a;
    bool flag = false;
    ll s = 0;
    cin >> n;
    REP(i, 0, n, 1) {
        cin >> a;
        if (A[a] == 0) v.pb(a);
        A[a]++;
        s += a;
    }
    sort(all(v));
    REP(i, 0, v.sz, 1) {
        pre[i] = (ll)A[v[i]] * (ll)v[i] + (i == 0 ? 0 : pre[i-1]);
        suf[i] = s - (i == 0 ? 0 : pre[i-1]);
    }
    REP(i, 1, v.sz, 1) {
        if (v[i] == v[i-1] + 1) {
            if (pre[i-1] == suf[i+1]) flag = true;
        }
        else {
            if (pre[i-1] == suf[i+1] or pre[i-1] == suf[i]) flag = true;
        }
        if (flag) break;
    }
    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 1e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define PQPGB priority_queue<pii ,vector< pll >, greater< pll > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

const int N =1e5+7;
int a[N];
int lidx[N];
ll sum[N];

int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);      
    #endif
    fast_io;
    int n; cin>>n;
    assert(n>=1 && n<=100000);
    mem(lidx,0);
    int mx=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        mx=max(a[i],mx);
        assert(a[i]>=1 && a[i]<=100000);
    }
    sort(a+1,a+n+1);
    sum[0]=0;
    for(int i=1;i<=n;i++) {
        lidx[a[i]]=i;
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<mx;i++) {
        int l=1,r=n;
        int idx1=0;
        while(l<=r) {
            int mid=(l+r)/2;
            if(a[mid]<i) idx1=mid,l=mid+1;
            else r=mid-1;
        }
        int idx2=0;
        l=1,r=n;
        while(l<=r) {
            int mid=(l+r)/2;
            if(a[mid]>i) r=mid-1,idx2=mid;
            else l=mid+1;
        }
        ll v1=sum[idx1];
        ll v2=sum[n]-sum[idx2-1];
        if(v1==v2) {
            cout<<"YES\n";
            return 0;
        }
    }
    cout<<"NO\n";

    return 0;
}