Submission #486098

#	Time	Username	Problem	Language	Result	Execution time	Memory
486098		Ronin13	Gift (IZhO18_nicegift)	C++14	100 / 100	559 ms	133412 KiB

nicegift

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

void solve(){
    int n;cin>>n;
    int k;cin>>k;
    ll a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    ll sum=0;
    ll mx=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        mx=max(mx,a[i]);
    }
    if(sum%(ll)k){
        cout<<-1<<"\n";
        return;
    }
    if(mx>sum/(ll)k){
        cout<<-1<<"\n";
        return;
    }
    vector<vector<pll> >vec(k+1);
    int ind=1;
    for(int i=1;i<=k;i++){
        ll left=sum/(ll)k;
        while(left>0){
            if(left>=a[ind])vec[i].pb({a[ind],ind}),left-=a[ind],ind++;
            else{
                a[ind]-=left,vec[i].pb({left,ind});
                left=0;
            }
        }
    }
    vector<int>idx(k+1,0);
    vector<vector<ll> >ans(n+1);
    ind=0;

    while(idx[1]<vec[1].size()){
        ll mn=linf;
        for(int i=1;i<=k;i++){
            int in=idx[i];
            mn=min(mn,vec[i][in].f);
        }
        vector<ll>xx;
        ans[ind].pb(mn);
        for(int i=1;i<=k;i++){
            ans[ind].pb(vec[i][idx[i]].s);
        }
        for(int i=1;i<=k;i++){
            int in=idx[i];
            vec[i][in].f-=mn;
            if(vec[i][in].f==0)idx[i]++;
        }
        ind++;
    }
    cout<<ind<<"\n";
    for(int i=0;i<ind;i++){
        for(ll to:ans[i])cout<<to<<" ";
        cout<<"\n";
    }

}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int test=1;//cin>>test;
    while(test--){
        solve();
    }
}

Compilation message (stderr)

nicegift.cpp: In function 'void solve()':
nicegift.cpp:49:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(idx[1]<vec[1].size()){

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