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 int long long
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N], pos[N];
main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
int sum = 0, mx = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
mx = max(mx, a[i]);
}
if(sum % k){
return cout << "-1", 0;
}
int val = sum / k;
if(mx > val){
return cout << "-1", 0;
}
sum = 0;
vector < vector < pair < int, int > > > q;
vector < pair < int, int > > cur;
for(int i = 1; i <= n; i++){
sum += a[i];
if(sum >= val){
cur.push_back(make_pair(a[i] - (sum - val), i));
q.push_back(cur);
cur.clear();
sum -= val;
if(sum > 0){
cur.push_back(make_pair(sum, i));
}
}
else{
cur.push_back(make_pair(a[i], i));
}
}
vector < vector < int > > ans;
while(true){
int mn = 9e18;
for(int i = 0; i < k; i++){
mn = min(mn, q[i][pos[i]].first);
}
bool flag = false;
vector < int > vec;
vec.push_back(mn);
for(int i = 0; i < k; i++){
vec.push_back(q[i][pos[i]].second);
q[i][pos[i]].first -= mn;
if(pos[i] < (int)q[i].size() && q[i][pos[i]].first == 0){
pos[i] += 1;
if(pos[i] < (int)q[i].size()){
flag = true;
}
}
}
ans.push_back(vec);
if(flag == false){
break;
}
}
cout << (int)ans.size() << "\n";
for(auto it : ans){
for(auto x : it){
cout << x << " ";
}
cout << "\n";
}
}
Compilation message (stderr)
nicegift.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# | 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... |