#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<ll,int> pii;
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define mkp make_pair
const int MAXN=1E6+10, MAX_OPS=3E6;
ll A[MAXN];
vector<ll> val;
vector<vector<int> > idx;
vector<int> now;
vector<pii> tmp;
int main(){ jizz
int n, k;
cin>>n>>k;
ll sum=0, mxa=0;
for(int i=1;i<=n;i++){
cin>>A[i];
sum+=A[i];
mxa=max(mxa,A[i]);
}
if(sum%k>0){
cout<<"-1\n";
return 0;
}
if(mxa>sum/k){
cout<<"-1\n";
return 0;
}
ll cur=0;
for(int i=1;i<=n;i++){
if(cur==0) now.pb(i);
cur=cur+A[i];
if(cur>sum/k){
now.pb(i);
cur-=sum/k;
}
tmp.pb(mkp(cur,now.size()-1));
}
sort(ALL(tmp));
ll last=0;
for(int i=0;i<n;i++){
//cout<<"hi "<<tmp[i].F<<" "<<tmp[i].S<<"\n";
if(tmp[i].F!=last){
val.pb(tmp[i].F-last);
idx.pb(now);
}
now[tmp[i].S]++;
last=tmp[i].F;
}
cout<<val.size()<<"\n";
for(int i=0;i<val.size();i++){
cout<<val[i]<<" ";
for(int j=0;j<k;j++){
cout<<idx[i][j]<<" \n"[j==k-1];
}
}
return 0;
}
Compilation message
nicegift.cpp: In function 'int main()':
nicegift.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<val.size();i++){
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
24 ms |
4836 KB |
n=50000 |
12 |
Correct |
32 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
1 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
492 KB |
n=623 |
16 |
Correct |
1 ms |
492 KB |
n=973 |
# |
결과 |
실행 시간 |
메모리 |
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 |
24 ms |
4836 KB |
n=50000 |
12 |
Correct |
32 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
1 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
492 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 |
3 ms |
492 KB |
n=592 |
20 |
Correct |
2 ms |
492 KB |
n=938 |
21 |
Correct |
2 ms |
492 KB |
n=747 |
22 |
Correct |
2 ms |
492 KB |
n=991 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
567 ms |
71384 KB |
n=1000000 |
2 |
Correct |
323 ms |
47968 KB |
n=666666 |
3 |
Correct |
163 ms |
25680 KB |
n=400000 |
4 |
Correct |
344 ms |
51392 KB |
n=285714 |
5 |
Correct |
10 ms |
1392 KB |
n=20000 |
6 |
Correct |
317 ms |
39376 KB |
n=181818 |
7 |
Correct |
5 ms |
1004 KB |
n=10000 |
8 |
Correct |
34 ms |
3692 KB |
n=6666 |
9 |
Correct |
2 ms |
620 KB |
n=4000 |
10 |
Correct |
190 ms |
17772 KB |
n=2857 |
11 |
Correct |
1 ms |
632 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
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 |
24 ms |
4836 KB |
n=50000 |
12 |
Correct |
32 ms |
4712 KB |
n=50000 |
13 |
Correct |
1 ms |
364 KB |
n=10 |
14 |
Correct |
1 ms |
492 KB |
n=685 |
15 |
Correct |
1 ms |
492 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 |
3 ms |
492 KB |
n=592 |
20 |
Correct |
2 ms |
492 KB |
n=938 |
21 |
Correct |
2 ms |
492 KB |
n=747 |
22 |
Correct |
2 ms |
492 KB |
n=991 |
23 |
Correct |
567 ms |
71384 KB |
n=1000000 |
24 |
Correct |
323 ms |
47968 KB |
n=666666 |
25 |
Correct |
163 ms |
25680 KB |
n=400000 |
26 |
Correct |
344 ms |
51392 KB |
n=285714 |
27 |
Correct |
10 ms |
1392 KB |
n=20000 |
28 |
Correct |
317 ms |
39376 KB |
n=181818 |
29 |
Correct |
5 ms |
1004 KB |
n=10000 |
30 |
Correct |
34 ms |
3692 KB |
n=6666 |
31 |
Correct |
2 ms |
620 KB |
n=4000 |
32 |
Correct |
190 ms |
17772 KB |
n=2857 |
33 |
Correct |
1 ms |
632 KB |
n=2000 |
34 |
Correct |
19 ms |
2920 KB |
n=23514 |
35 |
Correct |
18 ms |
2920 KB |
n=23514 |
36 |
Correct |
1 ms |
492 KB |
n=940 |
37 |
Correct |
1 ms |
364 KB |
n=2 |
38 |
Correct |
87 ms |
12512 KB |
n=100000 |
39 |
Correct |
99 ms |
12540 KB |
n=100000 |
40 |
Correct |
1 ms |
364 KB |
n=10 |
41 |
Correct |
1 ms |
364 KB |
n=100 |
42 |
Correct |
6 ms |
876 KB |
n=1000 |
43 |
Correct |
595 ms |
114100 KB |
n=1000000 |
44 |
Correct |
748 ms |
124536 KB |
n=1000000 |
45 |
Correct |
519 ms |
87712 KB |
n=666666 |
46 |
Correct |
392 ms |
57664 KB |
n=400000 |
47 |
Correct |
187 ms |
17516 KB |
n=2336 |
48 |
Correct |
347 ms |
51392 KB |
n=285714 |
49 |
Correct |
291 ms |
39500 KB |
n=181818 |
50 |
Correct |
214 ms |
23012 KB |
n=40000 |
51 |
Correct |
210 ms |
20992 KB |
n=20000 |
52 |
Correct |
221 ms |
18988 KB |
n=10000 |
53 |
Correct |
191 ms |
18540 KB |
n=6666 |
54 |
Correct |
189 ms |
17976 KB |
n=4000 |
55 |
Correct |
188 ms |
17772 KB |
n=2857 |
56 |
Correct |
181 ms |
16876 KB |
n=2000 |