1891C - Smilo and Monsters - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll > pi;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
#define endl '\n'
#define MP make_pair
#define PB push_back
#define p (ll)(1e9 + 7)
#define input(n,a) for(ll i = 0 ; i< n;i++) cin >> a[i];

ll inv(ll i);
ll add(ll a, ll b) { return (a % p + b % p) % p; }
ll sub(ll a, ll b) { return (a % p - b % p + p) % p; }
ll mul(ll a, ll b) { return (a % p * b % p) % p; }
ll divm(ll a, ll b) { return mul(a, inv(b)); }
ll inv(ll i) { return i <= 1 ? i : p - (p / i) * inv(p % i) % p; }

ll ceil(ll a ,ll b)
{
    ll x = a/b;
    if(a%b !=0) x++;
    return x;
}

ll power(ll a , ll b)
{
    if(b==0) return 1;
    ll x = power(a , b/2);
    if(b%2 == 0)  return x*x;
    else return x*x*a;
}

ll log(ll a , ll b )
{
    if(a/b > 0) return log(a/b , b) + 1;
    else return 0;
}

vb sieve(ll n)
{
    vector<bool> sieve(n + 1, true);
    vi ans;
    sieve[0] = false;
    sieve[1] = false;
    for(ll i = 2 ; i <= n;i++)
    {
        if (sieve[i])
        {
            for(ll j = 2*i ; j<= n;j+=i)  sieve[j] = false;
        }
    }
    //for (ll i = 1; i <= n; i++)
    //if (sieve[i])
        //ans.PB(i);
    return sieve;
}



typedef struct Hash
{
    vi power;
     ll A ;
    vi hash;
    ll n;
    const ll B = 1e9 + 7;
    Hash(string s, ll m)
    {
        n = s.length();
        power.resize( n + 1);
        hash.resize(n);
        A = m;
        hash[0] = s[0];
        power[0] = 1;
 
        for (ll i = 1; i <= n; i++)
        {
            power[i] = (power[i - 1] * A) % B;
        }
        for (ll i = 1; i < n; i++)
        {
            hash[i] = ((hash[i - 1] * A) % B + s[i] +B) % B;
        }
    }
    ll calcHash(ll i, ll j) // retrieves hash from i to j inclusive
    {
        if (i > 0)
            return (hash[j] - (hash[i - 1] * power[j - i  + 1]) % B + B) % B;
 
        return hash[j];
    }
} Hash;

typedef struct trienode
{   
    trienode* next[26];
    trienode()
    {
        for(ll i = 0 ; i< 26;i++) next[i] = NULL;
    }

    void add(char x)
    {
        ll ind = x - 'a';
        next[ind] = new trienode();
    }
    trienode* access(char x)
    {
        return next[x - 97];
    }
} trienode; 

//-------------------------------------------------------
//Instructions:-
//(1) Use a count array for once
//(2) Don't forget about the existence of 2 pollers :)
//(3) If subsequence of fixed number of elements is to be selected,sorted and using binary search may be a good idea
//(4) If nothing works, try to make  a recursion for DP
//(5) Knapsack when u have to maximize one parameter(value) taking care of other(weight or cost), or finding all possibilites among subsequences
//   -> the parameter must be of value and weights must be stored in array, which should be subracted till they are greater than 0, here dp[i] shows number of weights left after profit of i 
//                             or
//   -> the parameter must be of weights and profit must be stored in array, which should be added while index of weight must be subtracted,here dp[k] shows the minimum profit upon using weight k(not kth)
//(6) For O(n^2) , use smaller loop outside
//(7) We can find the number of operations like stuff ,with binary search for the answer and calling a boolean functionn of O(n) which tells if search should continue;
//    -> bin(n){ find(n);}
//    -> find(n){bin(n);}
//    -> refer https://codeforces.com/contest/1843/problem/E 
// (8) One more attempt, to try to binary search the answer, just find the function which needs to be optimized
//      then binary search on the possible number of operations and optimizing the function may be in O(n + m) (o/w TLE)
//    -> refer https://codeforces.com/contest/1843/problem/E 
// (9) While using dp, if there is some number of objects stuff ,we can have it as second parameter of
//      our dp state along with n
// (10) when numbers are some what like uptill 1024 500 etc. we can have dp state dp[n][500] ,
//      then we can use bit manipulations over them, to show which number is possible here(becomes a knapsack)
// (11) when we are asked about number of subarrays, we can use dp or prefix arryas(may be prefix of quantity as required),
//      and store some useful quantities to make use of prefixes
// (12) sometimes, finding maxima is difficult(binary search) because there are places where x1<=x2<x3 etc.
//      so to handle that, just make a mathematical equation of some variable and use binary search,(if 2 linear on 1 and binary on other)



//For Usaco , put this in main
//if (fopen("file.in", "r")) {
//	freopen("file.in", "r", stdin);
//	freopen("file.out", "w", stdout);
//}


void solve(ll i , vector<vector<ll>> & adj, vector<ll> &count, vector<vector<ll>> &v, ll * ans)
{

    for(ll x: adj[i])
    {
        for(ll j: v[x])
        {
            count[j-1]--;
            if(count[j-1] == 0)
            {
                *ans = *ans + 1;
            }
        }
        
    }   

}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        ll a[n];
        for(ll i = 0 ; i < n; i++)
        {
            cin >> a[i];
        }

        sort(a, a+n);

        ll i = 0 , j = n -1;
        ll x = 0;
        ll moves = 0;
        while( i <= j)
        {
            if(a[j]== x)
            {
                x = 0;
                a[j] = 0;
                moves++;
                j--;
                continue;
            }

            if(i == j)
            {
                if(a[i] == 1)
                {
                    moves++;
                    i++;
                    break;
                }
                ll k = (a[i] - x)/2 ;
                if(a[i] - x - 2*(k) == 1) k++;
                k++;
                i++;
                moves+=k;
                continue;
            }

            if(a[i] - a[j] + x > 0)
            {
                ll u = a[j] - x;
                x += u;
                a[i]-=u;
                moves+=u;
            }
            else
            {
                x+=a[i];
                moves+=a[i];
                a[i] = 0;
                
                i++;
            }

        }

        cout << moves<< endl;
    }
 

    return 0;
}