Educational Codeforces Round 21 (C. Tea Party)

 

Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

int fx[]= {1,-1,0,0};

int fy[]= {0,0,-1,1};

int main()

{

    int n,w,sum=0;

    cin>>n>>w;

    ll arr[n+9],bro[n+9],ans[n+9],vis[n+9],g=0;

    for(ll i=0; i<n; i++)

        cin>>arr[i],sum+=arr[i],bro[i]=arr[i],vis[i]=0;

    if(sum!=w)

    {

        sort(arr,arr+n);

        int extra=sum-w,last=0;

        for(int i=0; i<n; i++)

        {

            if(extra==0)

                ans[i]=arr[i];

            int need=ceil(arr[i]/2.0);

            if(need<last)

                need++;

            int removable=arr[i]-need;

            if(removable<=extra)

                ans[i]=need,extra-=removable;

            else

                ans[i]=arr[i]-extra,extra=0;

            last=need;

        }

    }

    else

    {

        for(int i=0; i<n; i++) ans[i]=arr[i];

    }

    for(int i=0; i<n; i++)

        g+=ans[i];

    if(g==w)

    {

        for(ll i=0; i<n; i++)

            for(ll j=0; j<n; j++)

                if(bro[i]==arr[j] && vis[j]==0)

                {

                    vis[j]=1;

                    cout<<ans[j]<<' ';

                    break;

                }

    }

    else

        cout<<"-1";

    cout<<endl;

    return 0;

}

///Alhamdulillah

Problem Link:https://codeforces.com/problemset/problem/808/C