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 <bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int n,k,a[N],mx,cur,sum,le,ri,mid,sum1,mx1,mn,anss;
vector < pii > v;
vector <int> ans[N];
int pas[N];
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>k;
for (int i = 1; i <= n; i++) {
cin>>a[i];
mx = max(mx,a[i]);
sum += a[i];
}
if (mx > sum / k || sum % k) {
cout<<"-1"<<endl;
return 0;
}
while (true) {
v.clear();
int sum1 = 0;
mx = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != 0) v.pb({a[i],i});
mx = max(mx,a[i]);
sum1 += a[i];
}
if (v.size() == 0) break;
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if (v.size() > k) mx1 = v[k].f;
else mx1 = 0;
mx = v[0].f; mn = v[k - 1].f;
le = 1;
ri = 1e5;
while(le <= ri) {
mid = (le + ri) / 2;
if (mn < mid || max(mx1,mx-mid)>(sum1 - k*mid)/k) {
ri = mid - 1;
} else {
anss = mid;
le = mid + 1;
}
}
cur++;
pas[cur] = anss;
for (int i = 0; i < k; i++) {
a[v[i].s] -= anss;
ans[cur].pb(v[i].s);
}
}
cout<<cur<<"\n";
for (int i = 1; i <= cur; i++) {
cout<<pas[i]<<" ";
for (int j = 0; j < ans[i].size(); j++) {
cout<<ans[i][j]<<" ";
}cout<<"\n";
}
}
Compilation message (stderr)
nicegift.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
13 | main() {
| ^~~~
nicegift.cpp: In function 'int main()':
nicegift.cpp:37:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
37 | if (v.size() > k) mx1 = v[k].f;
| ~~~~~~~~~^~~
nicegift.cpp:61:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int j = 0; j < ans[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |