oj.uz

Submission #483406

# Submission time Handle Problem Language Result Execution time Memory
483406 2021-10-29T08:40:46 Z mosiashvililuka Gift (IZhO18_nicegift) C++14
100 / 100
 542 ms 148972 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,k,f[1000009],X[1000009],T,dep,pi;
vector <vector <long long> > ans;
vector <long long> vv;
vector <pair <long long, long long> > v[1000009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>k;zx=0;xc=0;
	for(i=1; i<=a; i++){
		cin>>f[i];xc=max(xc,f[i]);
		zx+=f[i];
	}
	if(zx%k!=0){
		cout<<-1;exit(0);
	}
	if(xc*k>zx){
		cout<<-1;exit(0);
	}
	T=zx/k;
	j=1;jj=1;
	for(i=1; i<=a; ){
		if(jj>T){j++;jj=1;}
		if(T-jj+1>=f[i]){
			v[j].push_back(make_pair(f[i]+jj-1,i));jj+=f[i];
			i++;
			continue;
		}
		v[j].push_back(make_pair(T,i));f[i]-=T-jj+1;
		j++;jj=1;
	}
	dep=1;pi=0;
	while(dep<=T){
		pi++;vv.clear();X[pi]=1000000000000000000LL;
		for(i=1; i<=k; i++){
			c=lower_bound(v[i].begin(),v[i].end(),make_pair(dep,0LL))-v[i].begin();
			X[pi]=min(X[pi],v[i][c].first-dep+1);vv.push_back(v[i][c].second);
		}
		ans.push_back(vv);dep+=X[pi];
	}
	cout<<ans.size()<<"\n";
	for(i=0; i<ans.size(); i++){
		cout<<X[i+1]<<" ";
		for(j=0; j<k; j++){
			cout<<ans[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:42:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(i=0; i<ans.size(); i++){
      |           ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=4
2 Correct 12 ms 23756 KB n=3
3 Correct 13 ms 23748 KB n=3
4 Correct 12 ms 23756 KB n=4
5 Correct 12 ms 23756 KB n=4
6 Correct 12 ms 23756 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=4
2 Correct 12 ms 23756 KB n=3
3 Correct 13 ms 23748 KB n=3
4 Correct 12 ms 23756 KB n=4
5 Correct 12 ms 23756 KB n=4
6 Correct 12 ms 23756 KB n=2
7 Correct 11 ms 23756 KB n=5
8 Correct 12 ms 23756 KB n=8
9 Correct 12 ms 23740 KB n=14
10 Correct 12 ms 23812 KB n=11
11 Correct 32 ms 28192 KB n=50000
12 Correct 29 ms 28020 KB n=50000
13 Correct 12 ms 23756 KB n=10
14 Correct 12 ms 23884 KB n=685
15 Correct 16 ms 23836 KB n=623
16 Correct 16 ms 23876 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=4
2 Correct 12 ms 23756 KB n=3
3 Correct 13 ms 23748 KB n=3
4 Correct 12 ms 23756 KB n=4
5 Correct 12 ms 23756 KB n=4
6 Correct 12 ms 23756 KB n=2
7 Correct 11 ms 23756 KB n=5
8 Correct 12 ms 23756 KB n=8
9 Correct 12 ms 23740 KB n=14
10 Correct 12 ms 23812 KB n=11
11 Correct 32 ms 28192 KB n=50000
12 Correct 29 ms 28020 KB n=50000
13 Correct 12 ms 23756 KB n=10
14 Correct 12 ms 23884 KB n=685
15 Correct 16 ms 23836 KB n=623
16 Correct 16 ms 23876 KB n=973
17 Correct 13 ms 23916 KB n=989
18 Correct 11 ms 23884 KB n=563
19 Correct 14 ms 23904 KB n=592
20 Correct 13 ms 24128 KB n=938
21 Correct 12 ms 23892 KB n=747
22 Correct 14 ms 24012 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 92988 KB n=1000000
2 Correct 240 ms 70424 KB n=666666
3 Correct 141 ms 48816 KB n=400000
4 Correct 334 ms 78492 KB n=285714
5 Correct 21 ms 24952 KB n=20000
6 Correct 255 ms 68760 KB n=181818
7 Correct 14 ms 24304 KB n=10000
8 Correct 38 ms 28344 KB n=6666
9 Correct 16 ms 23936 KB n=4000
10 Correct 154 ms 49012 KB n=2857
11 Correct 16 ms 23884 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB n=4
2 Correct 12 ms 23756 KB n=3
3 Correct 13 ms 23748 KB n=3
4 Correct 12 ms 23756 KB n=4
5 Correct 12 ms 23756 KB n=4
6 Correct 12 ms 23756 KB n=2
7 Correct 11 ms 23756 KB n=5
8 Correct 12 ms 23756 KB n=8
9 Correct 12 ms 23740 KB n=14
10 Correct 12 ms 23812 KB n=11
11 Correct 32 ms 28192 KB n=50000
12 Correct 29 ms 28020 KB n=50000
13 Correct 12 ms 23756 KB n=10
14 Correct 12 ms 23884 KB n=685
15 Correct 16 ms 23836 KB n=623
16 Correct 16 ms 23876 KB n=973
17 Correct 13 ms 23916 KB n=989
18 Correct 11 ms 23884 KB n=563
19 Correct 14 ms 23904 KB n=592
20 Correct 13 ms 24128 KB n=938
21 Correct 12 ms 23892 KB n=747
22 Correct 14 ms 24012 KB n=991
23 Correct 417 ms 92988 KB n=1000000
24 Correct 240 ms 70424 KB n=666666
25 Correct 141 ms 48816 KB n=400000
26 Correct 334 ms 78492 KB n=285714
27 Correct 21 ms 24952 KB n=20000
28 Correct 255 ms 68760 KB n=181818
29 Correct 14 ms 24304 KB n=10000
30 Correct 38 ms 28344 KB n=6666
31 Correct 16 ms 23936 KB n=4000
32 Correct 154 ms 49012 KB n=2857
33 Correct 16 ms 23884 KB n=2000
34 Correct 23 ms 26388 KB n=23514
35 Correct 24 ms 26372 KB n=23514
36 Correct 12 ms 23800 KB n=940
37 Correct 11 ms 23804 KB n=2
38 Correct 87 ms 37560 KB n=100000
39 Correct 87 ms 37512 KB n=100000
40 Correct 11 ms 23756 KB n=10
41 Correct 12 ms 23788 KB n=100
42 Correct 19 ms 24396 KB n=1000
43 Correct 488 ms 138276 KB n=1000000
44 Correct 542 ms 148972 KB n=1000000
45 Correct 431 ms 111804 KB n=666666
46 Correct 342 ms 87760 KB n=400000
47 Correct 153 ms 48840 KB n=2336
48 Correct 304 ms 78644 KB n=285714
49 Correct 257 ms 68816 KB n=181818
50 Correct 263 ms 54828 KB n=40000
51 Correct 178 ms 52348 KB n=20000
52 Correct 175 ms 50280 KB n=10000
53 Correct 156 ms 49860 KB n=6666
54 Correct 149 ms 49248 KB n=4000
55 Correct 154 ms 49092 KB n=2857
56 Correct 146 ms 48212 KB n=2000