#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;
const int MAXN = 2000001;
vector<vector<ll>> ans;
vector<pair<int, ll>> g[MAXN];
ll a[MAXN];
int main() {
#ifdef PAUNSVOKNO
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
int n, k;
cin >> n >> k;
ll s = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s += a[i];
}
if (s % k) {
return cout << -1 << "\n", 0;
}
int cur = 0;
s /= k;
ll left = s;
for (int i = 1; i <= n; ++i) {
if (a[i] > s) {
return cout << -1 << "\n", 0;
}
if (a[i] >= left) {
g[cur++].emplace_back(i, left);
if (a[i] != left) {
g[cur].emplace_back(i, a[i] - left);
}
left += (s - a[i]);
} else {
g[cur].emplace_back(i, a[i]);
left -= a[i];
}
}
while (!g[0].empty()) {
ll x = (1ll << 60);
ans.emplace_back(k + 1);
for (int i = 0; i < k; ++i) {
ans.back()[i + 1] = g[i].back().first;
x = min(x, g[i].back().second);
}
ans.back()[0] = x;
for (int i = 0; i < k; ++i) {
if (x == g[i].back().second) {
g[i].pop_back();
} else {
g[i].back().second -= x;
}
}
}
cout << ans.size() << "\n";
for (auto& v : ans) {
for (auto& t : v) {
cout << t << " ";
}
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47224 KB |
n=4 |
2 |
Correct |
44 ms |
47336 KB |
n=3 |
3 |
Correct |
42 ms |
47376 KB |
n=3 |
4 |
Correct |
48 ms |
47488 KB |
n=4 |
5 |
Correct |
42 ms |
47616 KB |
n=4 |
6 |
Correct |
42 ms |
47736 KB |
n=2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47224 KB |
n=4 |
2 |
Correct |
44 ms |
47336 KB |
n=3 |
3 |
Correct |
42 ms |
47376 KB |
n=3 |
4 |
Correct |
48 ms |
47488 KB |
n=4 |
5 |
Correct |
42 ms |
47616 KB |
n=4 |
6 |
Correct |
42 ms |
47736 KB |
n=2 |
7 |
Correct |
42 ms |
47736 KB |
n=5 |
8 |
Correct |
43 ms |
47736 KB |
n=8 |
9 |
Correct |
46 ms |
47736 KB |
n=14 |
10 |
Correct |
51 ms |
47736 KB |
n=11 |
11 |
Correct |
65 ms |
51940 KB |
n=50000 |
12 |
Correct |
63 ms |
51940 KB |
n=50000 |
13 |
Correct |
42 ms |
51940 KB |
n=10 |
14 |
Correct |
43 ms |
51940 KB |
n=685 |
15 |
Correct |
54 ms |
51940 KB |
n=623 |
16 |
Correct |
46 ms |
51940 KB |
n=973 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47224 KB |
n=4 |
2 |
Correct |
44 ms |
47336 KB |
n=3 |
3 |
Correct |
42 ms |
47376 KB |
n=3 |
4 |
Correct |
48 ms |
47488 KB |
n=4 |
5 |
Correct |
42 ms |
47616 KB |
n=4 |
6 |
Correct |
42 ms |
47736 KB |
n=2 |
7 |
Correct |
42 ms |
47736 KB |
n=5 |
8 |
Correct |
43 ms |
47736 KB |
n=8 |
9 |
Correct |
46 ms |
47736 KB |
n=14 |
10 |
Correct |
51 ms |
47736 KB |
n=11 |
11 |
Correct |
65 ms |
51940 KB |
n=50000 |
12 |
Correct |
63 ms |
51940 KB |
n=50000 |
13 |
Correct |
42 ms |
51940 KB |
n=10 |
14 |
Correct |
43 ms |
51940 KB |
n=685 |
15 |
Correct |
54 ms |
51940 KB |
n=623 |
16 |
Correct |
46 ms |
51940 KB |
n=973 |
17 |
Correct |
43 ms |
51940 KB |
n=989 |
18 |
Correct |
43 ms |
51940 KB |
n=563 |
19 |
Correct |
46 ms |
51940 KB |
n=592 |
20 |
Correct |
45 ms |
51940 KB |
n=938 |
21 |
Correct |
45 ms |
51940 KB |
n=747 |
22 |
Correct |
53 ms |
51940 KB |
n=991 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
570 ms |
126824 KB |
n=1000000 |
2 |
Correct |
388 ms |
126824 KB |
n=666666 |
3 |
Correct |
249 ms |
126824 KB |
n=400000 |
4 |
Correct |
544 ms |
133136 KB |
n=285714 |
5 |
Correct |
60 ms |
133136 KB |
n=20000 |
6 |
Correct |
430 ms |
133136 KB |
n=181818 |
7 |
Correct |
58 ms |
133136 KB |
n=10000 |
8 |
Correct |
104 ms |
133136 KB |
n=6666 |
9 |
Correct |
44 ms |
133136 KB |
n=4000 |
10 |
Correct |
241 ms |
133136 KB |
n=2857 |
11 |
Correct |
43 ms |
133136 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
47224 KB |
n=4 |
2 |
Correct |
44 ms |
47336 KB |
n=3 |
3 |
Correct |
42 ms |
47376 KB |
n=3 |
4 |
Correct |
48 ms |
47488 KB |
n=4 |
5 |
Correct |
42 ms |
47616 KB |
n=4 |
6 |
Correct |
42 ms |
47736 KB |
n=2 |
7 |
Correct |
42 ms |
47736 KB |
n=5 |
8 |
Correct |
43 ms |
47736 KB |
n=8 |
9 |
Correct |
46 ms |
47736 KB |
n=14 |
10 |
Correct |
51 ms |
47736 KB |
n=11 |
11 |
Correct |
65 ms |
51940 KB |
n=50000 |
12 |
Correct |
63 ms |
51940 KB |
n=50000 |
13 |
Correct |
42 ms |
51940 KB |
n=10 |
14 |
Correct |
43 ms |
51940 KB |
n=685 |
15 |
Correct |
54 ms |
51940 KB |
n=623 |
16 |
Correct |
46 ms |
51940 KB |
n=973 |
17 |
Correct |
43 ms |
51940 KB |
n=989 |
18 |
Correct |
43 ms |
51940 KB |
n=563 |
19 |
Correct |
46 ms |
51940 KB |
n=592 |
20 |
Correct |
45 ms |
51940 KB |
n=938 |
21 |
Correct |
45 ms |
51940 KB |
n=747 |
22 |
Correct |
53 ms |
51940 KB |
n=991 |
23 |
Correct |
570 ms |
126824 KB |
n=1000000 |
24 |
Correct |
388 ms |
126824 KB |
n=666666 |
25 |
Correct |
249 ms |
126824 KB |
n=400000 |
26 |
Correct |
544 ms |
133136 KB |
n=285714 |
27 |
Correct |
60 ms |
133136 KB |
n=20000 |
28 |
Correct |
430 ms |
133136 KB |
n=181818 |
29 |
Correct |
58 ms |
133136 KB |
n=10000 |
30 |
Correct |
104 ms |
133136 KB |
n=6666 |
31 |
Correct |
44 ms |
133136 KB |
n=4000 |
32 |
Correct |
241 ms |
133136 KB |
n=2857 |
33 |
Correct |
43 ms |
133136 KB |
n=2000 |
34 |
Correct |
65 ms |
133136 KB |
n=23514 |
35 |
Correct |
68 ms |
133136 KB |
n=23514 |
36 |
Correct |
44 ms |
133136 KB |
n=940 |
37 |
Correct |
41 ms |
133136 KB |
n=2 |
38 |
Correct |
120 ms |
133136 KB |
n=100000 |
39 |
Correct |
139 ms |
133136 KB |
n=100000 |
40 |
Correct |
49 ms |
133136 KB |
n=10 |
41 |
Correct |
49 ms |
133136 KB |
n=100 |
42 |
Correct |
49 ms |
133136 KB |
n=1000 |
43 |
Correct |
717 ms |
190988 KB |
n=1000000 |
44 |
Correct |
748 ms |
208224 KB |
n=1000000 |
45 |
Correct |
609 ms |
208224 KB |
n=666666 |
46 |
Correct |
453 ms |
208224 KB |
n=400000 |
47 |
Correct |
235 ms |
208224 KB |
n=2336 |
48 |
Correct |
409 ms |
208224 KB |
n=285714 |
49 |
Correct |
390 ms |
208224 KB |
n=181818 |
50 |
Correct |
274 ms |
208224 KB |
n=40000 |
51 |
Correct |
238 ms |
208224 KB |
n=20000 |
52 |
Correct |
226 ms |
208224 KB |
n=10000 |
53 |
Correct |
231 ms |
208224 KB |
n=6666 |
54 |
Correct |
267 ms |
208224 KB |
n=4000 |
55 |
Correct |
275 ms |
208224 KB |
n=2857 |
56 |
Correct |
254 ms |
208224 KB |
n=2000 |