Submission #1150029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150029		aktilek	Gift (IZhO18_nicegift)	C++20	7 / 100	2092 ms	12360 KiB

nicegift

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 7;
const int R = 1e9 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int B = 320;

void solve() {
	int n, k;
	cin >> n >> k;
	
	bool subtask1 = true;
	
	int a[N];
	pair < int, int > b[N];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = {a[i], i};
		if (i > 1) {
			if (a[i] != a[i - 1]) subtask1 = false;
		}
	}
	
	if (subtask1) {
		if ((a[1] * n) % k == 0) {
			int t = n / k;
			t--;
			cout << t + 1 + a[1] << "\n";
			int l = 1, r = k;
			for (int i = 1; i <= n / k - 1; i++) {
				cout << a[1] << ' ';
				for (int j = l; j <= r; j++) {
					cout << j << ' ';
				}
				l = r + 1;
				r = l + k - 1;
				cout << '\n';
			}
			cout << a[1] - 1 << ' ';
			for (int i = l; i <= r; i++) {
				cout << i << ' ';
			}
			cout << '\n';
			int cur = l;
			for (int i = 1; i <= a[i]; i++) {
				cout << 1 << ' ';
				for (int j = 1; j <= k - (n % k); j++) {
					cout << cur << ' ';
					cur++;
				}
				
				for (int j = n; j > n - (n % k); j--) {
					cout << j << ' ';
				}
				cout << '\n';
			}
		} else {
			cout << -1 << '\n';
		}
		return;
	}
	
	sort(b + 1, b + n + 1);
	reverse(b + 1, b + n + 1);
	
	vector < pair < int, int >> ans;
	
	while (true) {
		if (b[k].F > 0) {
			ans.pb({b[1].S, b[2].S});
			b[1].F -= 1;
			b[2].F -= 1;
			sort(b + 1, b + n + 1);
			reverse(b + 1, b + n + 1);
		} else {
			break;
		}
	}
	
	bool ok = true;
	for (int i = 1; i <= n; i++) {
		if (b[i].F != 0) {
			ok = false;
			break;
		}
	}
	
	if (!ok) {
		cout << "-1\n";
	} else {
		reverse(all(ans));
		cout << ans.size() << '\n';
		for (auto x : ans) {
			if (x.F > x.S) swap(x.F, x.S);
			cout << 1 << ' ' << x.F << ' ' << x.S << ' '<< '\n';
		}
	}
	
	// 2 2 1 1
	
}

int main() {
  	// freopen("gates.in", "r", stdin);
  	// freopen("gates.out", "w", stdout);
  	Fast
  
  	int tc = 1;
  	// cin >> tc;
  
  	while (tc--) {
    	solve();
  	}
}

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