제출 #885413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885413		jcelin	Gift (IZhO18_nicegift)	C++14	100 / 100	1791 ms	121988 KiB

nicegift

#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define msi multiset<int>
#define si set<int>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int inf = 1e8 + 7;
const ll INF = 1e18 + 7;
const int logo = 30;
const int MAXN = 1e6 + 2;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

set<pll> act;
vector<vll> ans;
vll tr;

ll arr[MAXN];

void solve(){
	int n;
	ll k;
	cin >> n >> k;
	ll s = 0;
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		act.insert({arr[i], i});
		s += arr[i];
	}
	
	if(s % k or (*act.rbegin()).X > (ll)(s / k)){
		cout << -1 << "\n";
		return;
	}
	
	while(!act.empty()){
		ll tak = 0;
		tr.clear();
		for(int i=0; i<k; i++){
			pll cr = *act.rbegin();
			act.erase(--act.end());
			tr.PB(cr.Y);
			tak = cr.X;
		}
		
		if(act.size()) tak = min(tak, (ll)(s / k) - (ll)(*act.rbegin()).X);
		
		for(auto &i : tr){
			arr[i] -= (ll)tak;
			s -= (ll)tak;
			if(arr[i]) act.insert({(ll)arr[i], (ll)i});
		}
		
		reverse(all(tr));
		tr.PB(tak);
		reverse(all(tr));
		ans.PB(tr);
	}
	
	cout << ans.size() << "\n";
	for(auto &x : ans){
		for(auto &y : x) cout << y << " ";
		cout << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}

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