oj.uz

Submission #859067

# Submission time Handle Problem Language Result Execution time Memory
859067 2023-10-09T15:54:49 Z NaimSS Gift (IZhO18_nicegift) C++14
100 / 100
 1514 ms 112500 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define ff first 
#define ss second
using namespace std;
typedef long long ll;

const int N = 1e6 + 100;
ll a[N];
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;
	cin >> n >> k;
	ll sum=0;
	rep(i,0,n){
		cin >> a[i];
		sum += a[i];
	}
	if(sum%k != 0){
		cout << -1 << endl;
		return 0;
	}
	vector<pair<ll,vector<int>> > res;

	ll divi = sum/k;
	rep(i,0,n)if(a[i] > divi){
		cout << -1 << endl;
		return 0;
	}
	vector<vector<pair<ll,ll>>> nv;
	int pt=0;

	while(pt < n){
		ll need = divi;
		vector<pair<ll,ll>> here;
		while(need > 0){
			while(pt < n && a[pt]==0)pt++;
			assert(pt < n);
			ll put = min(a[pt], need);
			if(a[pt] > divi){
				cout << -1 << endl;
				return 0;
			}
			a[pt] -= put;
			need -= put;
			assert(put > 0 && need>=0 && a[pt] >= 0);
			here.pb({put , pt});
		}
		while(pt < n && a[pt]==0)pt++;
		nv.pb(here);
	}
	ll put = 0;
	while(divi > 0){
		ll mn = 1e18;
		for(auto &v : nv){
			mn = min(mn,v.back().ff);
		}
		divi -= mn;
		vector<int> here;
		for(auto &v : nv){
			here.pb(v.back().ss);
			v.back().ff -= mn;
			while(v.size() && v.back().ff == 0)v.pop_back();
		}
		assert(mn > 0);
		res.pb({mn, here});
	}
	cout << res.size() << endl;
	for(auto [X,v] : res){
		cout << X << " ";
		for(auto id : v)cout << id + 1<<" ";
		cout << endl;
	}
}

Compilation message

nicegift.cpp: In function 'int32_t main()':
nicegift.cpp:70:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for(auto [X,v] : res){
      |           ^
nicegift.cpp:53:5: warning: unused variable 'put' [-Wunused-variable]
   53 |  ll put = 0;
      |     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 344 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 1 ms 348 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 344 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 1 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Correct 0 ms 348 KB n=8
9 Correct 0 ms 348 KB n=14
10 Correct 0 ms 348 KB n=11
11 Correct 63 ms 7420 KB n=50000
12 Correct 59 ms 6468 KB n=50000
13 Correct 0 ms 344 KB n=10
14 Correct 1 ms 348 KB n=685
15 Correct 1 ms 348 KB n=623
16 Correct 2 ms 348 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 344 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 1 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Correct 0 ms 348 KB n=8
9 Correct 0 ms 348 KB n=14
10 Correct 0 ms 348 KB n=11
11 Correct 63 ms 7420 KB n=50000
12 Correct 59 ms 6468 KB n=50000
13 Correct 0 ms 344 KB n=10
14 Correct 1 ms 348 KB n=685
15 Correct 1 ms 348 KB n=623
16 Correct 2 ms 348 KB n=973
17 Correct 2 ms 344 KB n=989
18 Correct 1 ms 348 KB n=563
19 Correct 2 ms 604 KB n=592
20 Correct 2 ms 600 KB n=938
21 Correct 2 ms 344 KB n=747
22 Correct 2 ms 604 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 70720 KB n=1000000
2 Correct 410 ms 40164 KB n=666666
3 Correct 176 ms 21512 KB n=400000
4 Correct 544 ms 49740 KB n=285714
5 Correct 4 ms 1116 KB n=20000
6 Correct 393 ms 39708 KB n=181818
7 Correct 2 ms 604 KB n=10000
8 Correct 24 ms 3608 KB n=6666
9 Correct 1 ms 600 KB n=4000
10 Correct 115 ms 18064 KB n=2857
11 Correct 1 ms 344 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB n=4
2 Correct 0 ms 348 KB n=3
3 Correct 0 ms 348 KB n=3
4 Correct 0 ms 344 KB n=4
5 Correct 0 ms 348 KB n=4
6 Correct 1 ms 348 KB n=2
7 Correct 0 ms 348 KB n=5
8 Correct 0 ms 348 KB n=8
9 Correct 0 ms 348 KB n=14
10 Correct 0 ms 348 KB n=11
11 Correct 63 ms 7420 KB n=50000
12 Correct 59 ms 6468 KB n=50000
13 Correct 0 ms 344 KB n=10
14 Correct 1 ms 348 KB n=685
15 Correct 1 ms 348 KB n=623
16 Correct 2 ms 348 KB n=973
17 Correct 2 ms 344 KB n=989
18 Correct 1 ms 348 KB n=563
19 Correct 2 ms 604 KB n=592
20 Correct 2 ms 600 KB n=938
21 Correct 2 ms 344 KB n=747
22 Correct 2 ms 604 KB n=991
23 Correct 838 ms 70720 KB n=1000000
24 Correct 410 ms 40164 KB n=666666
25 Correct 176 ms 21512 KB n=400000
26 Correct 544 ms 49740 KB n=285714
27 Correct 4 ms 1116 KB n=20000
28 Correct 393 ms 39708 KB n=181818
29 Correct 2 ms 604 KB n=10000
30 Correct 24 ms 3608 KB n=6666
31 Correct 1 ms 600 KB n=4000
32 Correct 115 ms 18064 KB n=2857
33 Correct 1 ms 344 KB n=2000
34 Correct 36 ms 4896 KB n=23514
35 Correct 36 ms 4888 KB n=23514
36 Correct 2 ms 348 KB n=940
37 Correct 0 ms 348 KB n=2
38 Correct 185 ms 14528 KB n=100000
39 Correct 167 ms 13672 KB n=100000
40 Correct 0 ms 348 KB n=10
41 Correct 1 ms 348 KB n=100
42 Correct 4 ms 860 KB n=1000
43 Correct 1466 ms 109620 KB n=1000000
44 Correct 1514 ms 112500 KB n=1000000
45 Correct 1075 ms 81832 KB n=666666
46 Correct 757 ms 54456 KB n=400000
47 Correct 111 ms 17408 KB n=2336
48 Correct 543 ms 50028 KB n=285714
49 Correct 378 ms 38572 KB n=181818
50 Correct 174 ms 24288 KB n=40000
51 Correct 144 ms 21004 KB n=20000
52 Correct 123 ms 18716 KB n=10000
53 Correct 122 ms 18512 KB n=6666
54 Correct 113 ms 18004 KB n=4000
55 Correct 112 ms 17728 KB n=2857
56 Correct 112 ms 16872 KB n=2000