Submission #93299

#	Time	Username	Problem	Language	Result	Execution time	Memory
93299		Abelyan	Gift (IZhO18_nicegift)	C++17	100 / 100	1925 ms	203368 KiB

nicegift

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORR(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTR(i,a,b) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define fr first
#define sc second

const int N=2e6+6;
ll a[N],indcomp[N];
vector<pair<ll,int> > comp[N];
vector<ll> ans[N];
int main(){
    ios_base::sync_with_stdio(false);
    ll n,k;

    cin>>n>>k;
    ll sum=0;
    ll mx=0;
    FOR(i,n){
        cin>>a[i];
        //cout<<a[i]<<endl;
        sum+=a[i];
        mx=max(mx,(ll)a[i]);
    }
    //cout<<sum<<endl;
    if (sum%k!=0 || sum/k<mx){
        cout<<-1<<endl;
        return 0;
    }
    ll tv=0,sahm=sum/k,cnt=0;
    FOR(i,n){
        if (!a[i])continue;
        if (tv+a[i]>=sahm){
            comp[cnt].push_back({sahm-tv,i+1});
            a[i]-=sahm-tv;
            cnt++;
            tv=0;
            i--;
            continue;
        }
        comp[cnt].push_back({a[i],i+1});
        tv+=(ll)a[i];
    }
    int hert=0;
    while(sum){
        //cout<<sum<<endl;
        ll mn=LLONG_MAX;
        FOR(i,k){
            if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
            mn=min(mn,comp[i][indcomp[i]].fr);
        }
        ans[hert].push_back(mn);
        FOR(i,k){
            if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
            comp[i][indcomp[i]].fr-=mn;
            ans[hert].push_back(comp[i][indcomp[i]].sc);
            if (comp[i][indcomp[i]].fr==0)
                indcomp[i]++;
        }
        hert++;
        //if (hert>=N)break;
        sum-=(k*(ll)mn);
        //cout<<sum<<endl;
    }
    //cout<<sum<<endl;
    cout<<hert<<endl;
    FOR(i,hert){
        //cout<<ans[i].size()<<" ";
        trav(tt,ans[i])cout<<tt<<" ";
        cout<<endl;
    }
    return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
                 ~~~~~~~~~~^~~~~~~~~~~~~~~~
nicegift.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (indcomp[i]>=comp[i].size()){cout<<"hoy"<<endl;continue;}
                 ~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51