Submission #93167

#	Time	Username	Problem	Language	Result	Execution time	Memory
93167		Moysenko	Gift (IZhO18_nicegift)	C++17	7 / 100	569 ms	55092 KiB

nicegift

/*ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░ 
▄███▀░◐░░░▌░░░░░░░ 
░░░░▌░░░░░▐░░░░░░░ 
░░░░▐░░░░░▐░░░░░░░ 
░░░░▌░░░░░▐▄▄░░░░░ 
░░░░▌░░░░▄▀▒▒▀▀▀▀▄ 
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ 
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ 
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░░░▌▌░▌▌░░░░░ 
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
НАСТРОЙКА НА КРИТЫ ██████████████] 100% СОЧНОСТИ*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <chrono>
#include <ctime>
#include <unordered_set>
#include <random>
  
#define ep emplace_back
#define F first
#define S second
  
using namespace std;
  
typedef long long ll;
typedef long double ld;
const int inf = 1e9 + 7;
mt19937 rd(chrono :: system_clock :: now().time_since_epoch().count());
  
#pragma GCC optimize("unroll-loops") // развернуть цикл
#pragma GCC optimize("Ofast") // скомпилировать с о3
/*
#pragma GCC optimize("no-stack-protector") // что-то со стеком
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") // оптимизации процессора
#pragma GCC optimize("fast-math") // оптимизации сопроцессора
*/

const int siz = 1e6 + 10;
ll a[siz];
int n, k;

ll gcd(ll x, ll y){
	return (x ? gcd(y % x, x) : y);
}

void solve12(){
	if (n == 2){
		if (a[0] == a[1]){
			cout << "1\n" << a[0] << " 1 2";
			exit(0);
		}
		else{
			cout << -1;
			exit(0);
		}
	}

	ll all = 0;
	int i;
	for (i = 0; i < n; i++)
		all += a[i];

	if (all % (ll)k != 0){
		cout << -1;
		exit(0);
	}

	set<pair<int, int> > st;
	vector<int> dx, v, u;
	for (i = 0; i < n; i++)
		st.insert({a[i], i});

	if ((ll)(--st.end())->F * 2 > all){
		cout << -1;
		exit(0);
	}

	int ai;
	while (st.size() > 3){
		dx.ep(st.begin()->F);
		v.ep(st.begin()->S);
		u.ep((--st.end())->S);

		st.erase(st.begin());
		ai = (--st.end())->F, i = (--st.end())->S;
		st.erase(--st.end());
		if (ai - dx.back() > 0)
			st.insert({ai - dx.back(), i});
	}

	int A = st.begin()->F, B = (++st.begin())->F, C = (--st.end())->F;
	int Ai = st.begin()->S, Bi = (++st.begin())->S, Ci = (--st.end())->S;
	int D = (A + B - C) / 2;

	if (D > 0){
		dx.ep(D);
		v.ep(Ai);
		u.ep(Bi);
	}

	if (A - D > 0){
		dx.ep(A - D);
		v.ep(Ai);
		u.ep(Ci);
	}

	if (B - D > 0){
		dx.ep(B - D);
		v.ep(Bi);
		u.ep(Ci);
	}

	cout << dx.size() << '\n';
	for (i = 0; i < dx.size(); i++)
		cout << dx[i] << ' ' << v[i] + 1 << ' ' << u[i] + 1 << '\n';
}
 
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cin >> n >> k;
    int i;
    for (i = 0; i < n; i++)
    	cin >> a[i];

    if (k == 2){
    	solve12();
    	return 0;
    }

    ll x = gcd(a[0], k), y = gcd(n, k);
    if ((x * y) % k != 0){
    	cout << -1;
    	return 0;
    }

    y = k / x;
    ll A = a[0] / x, B = n / y;
    //cout << x << ' ' << A << '\n' << y << ' ' << B << '\n';
    int j;
    cout << B << '\n';
    for (i = 0; i < n; i++){
    	if (i % y == 0){
    		cout << A << ' ';
    		for (j = 0; j < k; j++)
    			cout << (i + j) % n + 1 << ' ';
    		cout << '\n';
    	}
    }

}

Compilation message (stderr)

nicegift.cpp: In function 'void solve12()':
nicegift.cpp:128:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < dx.size(); i++)
              ~~^~~~~~~~~~~

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