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:
- The number of coin(s) in each bag of the first group is strictly smaller than X.
- The number of coin(s) in each bag of the second group is strictly larger than X.
- 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("%dn",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lldn",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<<"YESn";
return 0;
}
}
cout<<"NOn";
return 0;
}