제출 #294535

#제출 시각아이디문제언어결과실행 시간메모리
294535nandonathanielGift (IZhO18_nicegift)C++14
100 / 100
709 ms147988 KiB
#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;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...