/*
-------------- | /
| | /
| | /
| * |/ | | ------ *
| | | | / \
| | |\ | | | |\ |
\ | | | \ | | | | \ |
\ | | | \ | | \ / \ |
V | | \ \__/| ----- \ |
*/
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
/*--------------------------------------------------------------------------------------*/
signed main() { EmiliaMyWife
int n, k;
cin >> n >> k;
vector<ll> arr(n);
ll sum = 0, mx = 0;
for(int i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i];
mx = max(mx, arr[i]);
}
if(sum % k || mx > sum / k)
return cout << "-1\n", 0;
ll len = sum / k;
ll s = 0;
vector<ll> v, owo(n);
for(int i = 0; i < n; i++) {
s += arr[i];
v.push_back(s % len ? s % len : len);
owo[i] = s;
}
vector<pair<ll, vector<int>>> ans;
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
ll prv = 0;
for(ll x : v) {
vector<int> tmp(k);
for(int i = 0; i < k; i++) {
tmp[i] = lower_bound(owo.begin(), owo.end(), x + len * i) - owo.begin();
}
ans.push_back({x - prv, tmp});
prv = x;
}
cout << ans.size() << '\n';
for(const auto &[x, y] : ans) {
cout << x;
for(auto w : y)
cout << ' ' << w + 1;
cout << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n=4 |
2 |
Correct |
1 ms |
364 KB |
n=3 |
3 |
Correct |
1 ms |
364 KB |
n=3 |
4 |
Correct |
1 ms |
364 KB |
n=4 |
5 |
Correct |
1 ms |
364 KB |
n=4 |
6 |
Correct |
1 ms |
364 KB |
n=2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n=4 |
2 |
Correct |
1 ms |
364 KB |
n=3 |
3 |
Correct |
1 ms |
364 KB |
n=3 |
4 |
Correct |
1 ms |
364 KB |
n=4 |
5 |
Correct |
1 ms |
364 KB |
n=4 |
6 |
Correct |
1 ms |
364 KB |
n=2 |
7 |
Correct |
1 ms |
364 KB |
n=5 |
8 |
Correct |
1 ms |
364 KB |
n=8 |
9 |
Correct |
1 ms |
364 KB |
n=14 |
10 |
Correct |
1 ms |
364 KB |
n=11 |
11 |
Correct |
28 ms |
4836 KB |
n=50000 |
12 |
Correct |
28 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
2 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
364 KB |
n=623 |
16 |
Correct |
1 ms |
492 KB |
n=973 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n=4 |
2 |
Correct |
1 ms |
364 KB |
n=3 |
3 |
Correct |
1 ms |
364 KB |
n=3 |
4 |
Correct |
1 ms |
364 KB |
n=4 |
5 |
Correct |
1 ms |
364 KB |
n=4 |
6 |
Correct |
1 ms |
364 KB |
n=2 |
7 |
Correct |
1 ms |
364 KB |
n=5 |
8 |
Correct |
1 ms |
364 KB |
n=8 |
9 |
Correct |
1 ms |
364 KB |
n=14 |
10 |
Correct |
1 ms |
364 KB |
n=11 |
11 |
Correct |
28 ms |
4836 KB |
n=50000 |
12 |
Correct |
28 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
2 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
364 KB |
n=623 |
16 |
Correct |
1 ms |
492 KB |
n=973 |
17 |
Correct |
1 ms |
492 KB |
n=989 |
18 |
Correct |
1 ms |
492 KB |
n=563 |
19 |
Correct |
2 ms |
492 KB |
n=592 |
20 |
Correct |
3 ms |
492 KB |
n=938 |
21 |
Correct |
3 ms |
492 KB |
n=747 |
22 |
Correct |
3 ms |
524 KB |
n=991 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
590 ms |
79800 KB |
n=1000000 |
2 |
Correct |
346 ms |
48084 KB |
n=666666 |
3 |
Correct |
176 ms |
25692 KB |
n=400000 |
4 |
Correct |
438 ms |
50368 KB |
n=285714 |
5 |
Correct |
9 ms |
1540 KB |
n=20000 |
6 |
Correct |
391 ms |
39660 KB |
n=181818 |
7 |
Correct |
5 ms |
876 KB |
n=10000 |
8 |
Correct |
58 ms |
3564 KB |
n=6666 |
9 |
Correct |
2 ms |
620 KB |
n=4000 |
10 |
Correct |
267 ms |
17772 KB |
n=2857 |
11 |
Correct |
1 ms |
492 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
n=4 |
2 |
Correct |
1 ms |
364 KB |
n=3 |
3 |
Correct |
1 ms |
364 KB |
n=3 |
4 |
Correct |
1 ms |
364 KB |
n=4 |
5 |
Correct |
1 ms |
364 KB |
n=4 |
6 |
Correct |
1 ms |
364 KB |
n=2 |
7 |
Correct |
1 ms |
364 KB |
n=5 |
8 |
Correct |
1 ms |
364 KB |
n=8 |
9 |
Correct |
1 ms |
364 KB |
n=14 |
10 |
Correct |
1 ms |
364 KB |
n=11 |
11 |
Correct |
28 ms |
4836 KB |
n=50000 |
12 |
Correct |
28 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
2 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
364 KB |
n=623 |
16 |
Correct |
1 ms |
492 KB |
n=973 |
17 |
Correct |
1 ms |
492 KB |
n=989 |
18 |
Correct |
1 ms |
492 KB |
n=563 |
19 |
Correct |
2 ms |
492 KB |
n=592 |
20 |
Correct |
3 ms |
492 KB |
n=938 |
21 |
Correct |
3 ms |
492 KB |
n=747 |
22 |
Correct |
3 ms |
524 KB |
n=991 |
23 |
Correct |
590 ms |
79800 KB |
n=1000000 |
24 |
Correct |
346 ms |
48084 KB |
n=666666 |
25 |
Correct |
176 ms |
25692 KB |
n=400000 |
26 |
Correct |
438 ms |
50368 KB |
n=285714 |
27 |
Correct |
9 ms |
1540 KB |
n=20000 |
28 |
Correct |
391 ms |
39660 KB |
n=181818 |
29 |
Correct |
5 ms |
876 KB |
n=10000 |
30 |
Correct |
58 ms |
3564 KB |
n=6666 |
31 |
Correct |
2 ms |
620 KB |
n=4000 |
32 |
Correct |
267 ms |
17772 KB |
n=2857 |
33 |
Correct |
1 ms |
492 KB |
n=2000 |
34 |
Correct |
19 ms |
2916 KB |
n=23514 |
35 |
Correct |
19 ms |
2916 KB |
n=23514 |
36 |
Correct |
1 ms |
492 KB |
n=940 |
37 |
Correct |
1 ms |
364 KB |
n=2 |
38 |
Correct |
107 ms |
12548 KB |
n=100000 |
39 |
Correct |
111 ms |
12508 KB |
n=100000 |
40 |
Correct |
1 ms |
364 KB |
n=10 |
41 |
Correct |
1 ms |
364 KB |
n=100 |
42 |
Correct |
9 ms |
876 KB |
n=1000 |
43 |
Correct |
675 ms |
114112 KB |
n=1000000 |
44 |
Correct |
813 ms |
124572 KB |
n=1000000 |
45 |
Correct |
611 ms |
87756 KB |
n=666666 |
46 |
Correct |
487 ms |
57792 KB |
n=400000 |
47 |
Correct |
269 ms |
17516 KB |
n=2336 |
48 |
Correct |
449 ms |
50548 KB |
n=285714 |
49 |
Correct |
393 ms |
39380 KB |
n=181818 |
50 |
Correct |
294 ms |
23140 KB |
n=40000 |
51 |
Correct |
274 ms |
21012 KB |
n=20000 |
52 |
Correct |
260 ms |
18916 KB |
n=10000 |
53 |
Correct |
266 ms |
18592 KB |
n=6666 |
54 |
Correct |
254 ms |
17936 KB |
n=4000 |
55 |
Correct |
266 ms |
17684 KB |
n=2857 |
56 |
Correct |
262 ms |
16876 KB |
n=2000 |