oj.uz

Submission #294535

# Submission time Handle Problem Language Result Execution time Memory
294535 2020-09-09T04:10:53 Z nandonathaniel Gift (IZhO18_nicegift) C++14
100 / 100
 709 ms 147988 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
typedef pair<LL,vector<LL> > piv;
const LL MAXN=1e6+5;

LL a[MAXN],sum[MAXN];
vector<pii> tumpukkan[MAXN];
vector<piv> ans;

/*
kita buat K stacks, each height total/K, such that at a height H, gada yang sama di K stacks itu 
itu bisa dibuat secara greedy sehingga 1 element exist di maximal 2 stack, dan gada intersection nya
Visualisasi ada di PPT nya Berted
Construct jawabannya dari atas kita gabung2in yang sama
*/

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,k,tot=0;
	cin >> n >> k;
	for(LL i=1;i<=n;i++){
		cin >> a[i];
		tot+=a[i];
	}
	if(tot%k!=0){
		cout << -1 << '\n';
		return 0;
	}
	for(LL i=1;i<=n;i++){
		if(a[i]>tot/k){
			cout << -1 << '\n';
			return 0;
		}
	}
	for(LL i=1;i<=n;i++){
		for(LL j=1;j<=k;j++){
			if(a[i]==0)break;
			if(sum[j]+a[i]<=tot/k){
				tumpukkan[j].push_back({a[i],i});
				sum[j]+=a[i];
				a[i]=0;
			}
			else if(sum[j]<tot/k){
				tumpukkan[j].push_back({tot/k-sum[j],i});
				a[i]-=(tot/k-sum[j]);
				sum[j]=tot/k;
			}
		}
	}
	while(!tumpukkan[1].empty()){
		LL sama=1e18;  //ada berapa baris yang sama
		for(LL i=1;i<=k;i++)sama=min(sama,tumpukkan[i].back().first);
		ans.push_back(piv());
		ans.back().first=sama;
		for(LL i=1;i<=k;i++){
			ans.back().second.push_back(tumpukkan[i].back().second);
			tumpukkan[i].back().first-=sama;
			if(tumpukkan[i].back().first==0)tumpukkan[i].pop_back();
		}
	}
	cout << ans.size() << '\n';
	for(auto isi : ans){
		cout << isi.first;
		for(auto isi2 : isi.second)cout << " " << isi2;
		cout << '\n';
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB n=4
2 Correct 16 ms 23808 KB n=3
3 Correct 16 ms 23808 KB n=3
4 Correct 16 ms 23808 KB n=4
5 Correct 16 ms 23808 KB n=4
6 Correct 16 ms 23808 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB n=4
2 Correct 16 ms 23808 KB n=3
3 Correct 16 ms 23808 KB n=3
4 Correct 16 ms 23808 KB n=4
5 Correct 16 ms 23808 KB n=4
6 Correct 16 ms 23808 KB n=2
7 Correct 16 ms 23808 KB n=5
8 Correct 16 ms 23808 KB n=8
9 Correct 17 ms 23936 KB n=14
10 Correct 16 ms 23808 KB n=11
11 Correct 41 ms 28400 KB n=50000
12 Correct 39 ms 28152 KB n=50000
13 Correct 16 ms 23808 KB n=10
14 Correct 17 ms 23936 KB n=685
15 Correct 17 ms 23936 KB n=623
16 Correct 17 ms 23936 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB n=4
2 Correct 16 ms 23808 KB n=3
3 Correct 16 ms 23808 KB n=3
4 Correct 16 ms 23808 KB n=4
5 Correct 16 ms 23808 KB n=4
6 Correct 16 ms 23808 KB n=2
7 Correct 16 ms 23808 KB n=5
8 Correct 16 ms 23808 KB n=8
9 Correct 17 ms 23936 KB n=14
10 Correct 16 ms 23808 KB n=11
11 Correct 41 ms 28400 KB n=50000
12 Correct 39 ms 28152 KB n=50000
13 Correct 16 ms 23808 KB n=10
14 Correct 17 ms 23936 KB n=685
15 Correct 17 ms 23936 KB n=623
16 Correct 17 ms 23936 KB n=973
17 Correct 17 ms 23936 KB n=989
18 Correct 17 ms 23936 KB n=563
19 Correct 18 ms 24064 KB n=592
20 Correct 18 ms 24064 KB n=938
21 Correct 18 ms 24064 KB n=747
22 Correct 19 ms 24064 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 106296 KB n=1000000
2 Correct 292 ms 73932 KB n=666666
3 Correct 185 ms 51412 KB n=400000
4 Correct 407 ms 82992 KB n=285714
5 Correct 38 ms 25088 KB n=20000
6 Correct 357 ms 77144 KB n=181818
7 Correct 35 ms 24440 KB n=10000
8 Correct 66 ms 30328 KB n=6666
9 Correct 33 ms 24056 KB n=4000
10 Correct 223 ms 56440 KB n=2857
11 Correct 31 ms 24064 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB n=4
2 Correct 16 ms 23808 KB n=3
3 Correct 16 ms 23808 KB n=3
4 Correct 16 ms 23808 KB n=4
5 Correct 16 ms 23808 KB n=4
6 Correct 16 ms 23808 KB n=2
7 Correct 16 ms 23808 KB n=5
8 Correct 16 ms 23808 KB n=8
9 Correct 17 ms 23936 KB n=14
10 Correct 16 ms 23808 KB n=11
11 Correct 41 ms 28400 KB n=50000
12 Correct 39 ms 28152 KB n=50000
13 Correct 16 ms 23808 KB n=10
14 Correct 17 ms 23936 KB n=685
15 Correct 17 ms 23936 KB n=623
16 Correct 17 ms 23936 KB n=973
17 Correct 17 ms 23936 KB n=989
18 Correct 17 ms 23936 KB n=563
19 Correct 18 ms 24064 KB n=592
20 Correct 18 ms 24064 KB n=938
21 Correct 18 ms 24064 KB n=747
22 Correct 19 ms 24064 KB n=991
23 Correct 455 ms 106296 KB n=1000000
24 Correct 292 ms 73932 KB n=666666
25 Correct 185 ms 51412 KB n=400000
26 Correct 407 ms 82992 KB n=285714
27 Correct 38 ms 25088 KB n=20000
28 Correct 357 ms 77144 KB n=181818
29 Correct 35 ms 24440 KB n=10000
30 Correct 66 ms 30328 KB n=6666
31 Correct 33 ms 24056 KB n=4000
32 Correct 223 ms 56440 KB n=2857
33 Correct 31 ms 24064 KB n=2000
34 Correct 30 ms 26348 KB n=23514
35 Correct 30 ms 26356 KB n=23514
36 Correct 17 ms 23936 KB n=940
37 Correct 16 ms 23808 KB n=2
38 Correct 114 ms 40664 KB n=100000
39 Correct 112 ms 40664 KB n=100000
40 Correct 16 ms 23808 KB n=10
41 Correct 17 ms 23936 KB n=100
42 Correct 21 ms 24696 KB n=1000
43 Correct 609 ms 137492 KB n=1000000
44 Correct 709 ms 147988 KB n=1000000
45 Correct 597 ms 121796 KB n=666666
46 Correct 469 ms 99928 KB n=400000
47 Correct 214 ms 51960 KB n=2336
48 Correct 401 ms 82760 KB n=285714
49 Correct 356 ms 77192 KB n=181818
50 Correct 258 ms 59364 KB n=40000
51 Correct 245 ms 56684 KB n=20000
52 Correct 227 ms 54640 KB n=10000
53 Correct 231 ms 60916 KB n=6666
54 Correct 216 ms 49784 KB n=4000
55 Correct 229 ms 56564 KB n=2857
56 Correct 210 ms 48632 KB n=2000