Submission #378859

#	Time	Username	Problem	Language	Result	Execution time	Memory
378859		YJU	Gift (IZhO18_nicegift)	C++14	100 / 100	1120 ms	89836 KiB

nicegift

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define ALL(_a) _a.begin(),_a.end()
#define SZ(_a) (ll)_a.size()

ll n,k,u[N],sum;
priority_queue<pll> pq;
vector<pair<ll,vector<ll> > > ans;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    REP1(i,n)cin>>u[i],pq.push(mp(u[i],i)),sum+=u[i];
    while(SZ(pq)>=k){
		vector<ll> cho;
		ll mx1,mx2;
        REP(i,k){
			pll nd=pq.top();
			mx1=nd.X;
			cho.pb(nd.Y);
            pq.pop();
        }
        mx2=pq.top().X;
        ll x=min(mx1,(SZ(pq)?(sum-mx2*k)/k:INF));
        ans.pb(mp(x,cho));
        sum-=x*k;
        REP(i,k){
			u[cho[i]]-=x;
			if(u[cho[i]])pq.push(mp(u[cho[i]],cho[i]));
        }
    }
	if(!SZ(pq)){
		cout<<SZ(ans)<<"\n";
		for(auto i:ans){
			cout<<i.X;
			for(auto j:i.Y)cout<<" "<<j;
			cout<<"\n";
		}
	}else{
		cout<<"-1\n";
	}
	return 0;
}

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:31:6: warning: 'mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   ll mx1,mx2;
      |      ^~~

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