Submission #1159950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159950		aktilek	Gift (IZhO18_nicegift)	C++20	18 / 100	40 ms	20928 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 = 5e5 + 7;
const int R = 1e9 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int B = 320;

vector < int > pos[N];

void solve() {
	int n, k;
	cin >> n >> k;
	
	int a[N];
	
	multiset < int > mlts;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mlts.insert(a[i]);
		pos[a[i]].pb(i);
	}
	
	vector < pair< int, int > > ans;
	
	while (true) {
		auto it = mlts.end();
		it--;
		int f = *it;
		it--;
		int s = *it;
		
		if (s > 0) {
			int fi = pos[f].back();
			pos[f].pop_back();
			int si = pos[s].back();
			pos[s].pop_back();
			f--;
			s--;
			pos[f].pb(fi);
			pos[s].pb(si);
			ans.pb({fi, si});
			mlts.erase(mlts.find(f + 1));
	        mlts.erase(mlts.find(s + 1));
	
	        mlts.insert(f);
	        mlts.insert(s);
		} else {
			break;
		}
	}
	
	reverse(all(ans));
	int b[N];
	for (int i = 1; i <= n; i++) {
		b[i] = 0;
	}
	for (pair < int, int > p : ans) {
		b[p.F]++;
		b[p.S]++;
	}
	
	bool ok = true;
	for (int i = 1; i <= n; i++) {
		if (b[i] != a[i]) {
			ok = false;
			break;
		}
	}
	
	if (ok) {
		cout << ans.size() << '\n';
		for (pair < int, int > p : ans) {
			cout << 1 << ' ' << p.F << ' ' << p.S << '\n';
		}
	} else {
		cout << -1 << '\n';
	}

}

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

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