| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 170887 | emil_physmath | Gift (IZhO18_nicegift) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef double ldouble;
typedef long long llong;
const int maxN = 100001;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<llong> arr(n);
multiset<pair<llong, int>> a;
llong mx = -1, sum = 0;
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
sum += arr[i];
mx = max(mx, arr[i]);
a.insert({arr[i], i});
}
if (sum % k || mx > sum / k)
{
cout << -1 << endl;
exit(0);
}
vector<pair<llong, vector<int>>> ans;
while (a.rbegin()->first)
{
vector<int> cur;
llong mn = a.rbegin()->first;
auto it = a.rbegin();
for (; cur.size() < k; ++it)
{
cur.push_back(it->second);
mn = min(mn, it->first);
}
if (it != a.rend())
mn = min(mn, a.rbegin()->first - *it + 1);
/*
if (!mn)
{
cout << -1 << endl;
exit(0);
}
*/
for (int x: cur)
{
a.erase({arr[x], x});
a.insert({arr[x] -= mn, x});
}
ans.push_back({mn, cur});
/*cerr << "a` ";
for (pair<llong, int> i: a)
cerr << i.first << ' ';
cerr << endl;*/
}
cout << ans.size() << '\n';
for (auto x: ans)
{
cout << x.first << ' ';
for (int y: x.second)
cout << y + 1 << ' ';
cout << '\n';
}
}
// 6 5 4 3 x
// x x-1 x-2 x-3 x