제출 #294535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294535		nandonathaniel	Gift (IZhO18_nicegift)	C++14	100 / 100	709 ms	147988 KiB

nicegift

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
typedef pair<LL,vector<LL> > piv;
const LL MAXN=1e6+5;

LL a[MAXN],sum[MAXN];
vector<pii> tumpukkan[MAXN];
vector<piv> ans;

/*
kita buat K stacks, each height total/K, such that at a height H, gada yang sama di K stacks itu 
itu bisa dibuat secara greedy sehingga 1 element exist di maximal 2 stack, dan gada intersection nya
Visualisasi ada di PPT nya Berted
Construct jawabannya dari atas kita gabung2in yang sama
*/

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,k,tot=0;
	cin >> n >> k;
	for(LL i=1;i<=n;i++){
		cin >> a[i];
		tot+=a[i];
	}
	if(tot%k!=0){
		cout << -1 << '\n';
		return 0;
	}
	for(LL i=1;i<=n;i++){
		if(a[i]>tot/k){
			cout << -1 << '\n';
			return 0;
		}
	}
	for(LL i=1;i<=n;i++){
		for(LL j=1;j<=k;j++){
			if(a[i]==0)break;
			if(sum[j]+a[i]<=tot/k){
				tumpukkan[j].push_back({a[i],i});
				sum[j]+=a[i];
				a[i]=0;
			}
			else if(sum[j]<tot/k){
				tumpukkan[j].push_back({tot/k-sum[j],i});
				a[i]-=(tot/k-sum[j]);
				sum[j]=tot/k;
			}
		}
	}
	while(!tumpukkan[1].empty()){
		LL sama=1e18;  //ada berapa baris yang sama
		for(LL i=1;i<=k;i++)sama=min(sama,tumpukkan[i].back().first);
		ans.push_back(piv());
		ans.back().first=sama;
		for(LL i=1;i<=k;i++){
			ans.back().second.push_back(tumpukkan[i].back().second);
			tumpukkan[i].back().first-=sama;
			if(tumpukkan[i].back().first==0)tumpukkan[i].pop_back();
		}
	}
	cout << ans.size() << '\n';
	for(auto isi : ans){
		cout << isi.first;
		for(auto isi2 : isi.second)cout << " " << isi2;
		cout << '\n';
	}
	return 0;
}

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