#include <bits/stdc++.h>
#define pb push_back
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int M = 1e5;
int n, k, a[N], uk[N];
vector < pii > m[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 != 0 || mx * k > sum) {
cout << -1;
return 0;
}
sum /= k;
int cur = 0, last = 1;
for(int i = 1; i <= n; i++) {
if(cur + a[i] == sum) {
m[last].pb({a[i], i});
cur = 0;
last++;
} else if(cur + a[i] > sum) {
m[last].pb({sum - cur, i});
last++;
m[last].pb({a[i] - sum + cur, i});
cur = a[i] - sum + cur;
} else {
m[last].pb({a[i], i});
cur += a[i];
}
}
if(m[last].empty()) last--;
srand(time(0));
random_shuffle(a + 1, a + n + 1);
vector < pair < int, vector < int > > > ans;
while(true) {
bool ok = 0;
ll mn = 1e18;
for(int block = 1; block <= last; block++) {
int l = uk[block];
if(l == m[block].size()) {
ok = 1;
break;
}
mn = min(m[block][l].first, mn);
}
if(ok) break;
vector < int > v;
for(int block = 1; block <= last; block++) {
int l = uk[block];
v.pb(m[block][l].second);
m[block][l].first -= mn;
if(m[block][l].first == 0) uk[block]++;
}
ans.pb({mn, v});
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i++) {
cout << ans[i].first;
vector < int > v = ans[i].second;
for(int j = 0; j < v.size(); j++) {
cout << " " << v[j];
}
cout << endl;
}
}
/*
5
2 8 5 1 10
5
2 3 5 3
2 5 3 3
1 4 4
2 3 4 2
1 1 2
*/
Compilation message
chessboard.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
20 | main() {
| ^~~~
chessboard.cpp: In function 'int main()':
chessboard.cpp:61:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if(l == m[block].size()) {
| ~~^~~~~~~~~~~~~~~~~~
chessboard.cpp:78:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
chessboard.cpp:81:26: 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]
81 | for(int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
47940 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
47940 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
