oj.uz

Submission #495468

# Submission time Handle Problem Language Result Execution time Memory
495468 2021-12-18T17:56:03 Z vinnipuh01 Gift (IZhO18_nicegift) C++17
100 / 100
 905 ms 156920 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
 
using namespace std;
 
const long long oo = 1000000000000000000;
 
long long  sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
 
    freopen ( "sum.in", "r", stdin )
*/
 
deque <pair<int, int> > v[ 100001 ];
vector <vector < int > > v1;
vector <int> vv;
 
main () {
	int n, m;
	cin >> n >> m;
	int a[ n + 1 ];
	for ( int i = 0; i < n; i ++ ) {
		cin >> a[ i ];
		sum += a[ i ];
		mx = max( mx, a[ i ] );
	}
	if ( sum % m != 0 || mx > sum / m )
		cout << "-1";
	else {
		pos = 1;
		for ( int i = 0; i < n; i ++ ) {
			if ( num == sum / m ) {
				num = 0;
				pos ++;
			}
			num += a[ i ];
			if ( num > sum / m ) {
				num -= a[ i ];
				v[ pos ].push_back( { ( sum / m ) - num, i } );
				num = a[ i ] - ( sum / m - num );
				pos ++;
				v[ pos ].push_back( { num, i } );
			}
			else {
				v[ pos ].push_back( { a[ i ], i } );
			}
		}
		while ( true ) {
			num = oo;
			for ( int i = 1; i <= pos; i ++ ) {
				num = min( num, v[ i ].front().first + 0ll );
			}
			ans += num;
			vv.clear();
			vv.push_back( num );
			for ( int i = 1; i <= pos; i ++ ) {
				vv.push_back( v[ i ].front().second + 1 );
				v[ i ].front().first -= num;
				if ( !v[ i ].front().first )
					v[ i ].pop_front();
			}
			v1.push_back( vv );
			if ( ans == sum / m )
				break;
		}
		cout << v1.size() << "\n";
		for ( auto i : v1 ) {
			for ( auto j : i )
				cout << j << " ";
			cout << "\n";
		}
	}
}

Compilation message

nicegift.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main () {
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 67528 KB n=4
2 Correct 38 ms 67504 KB n=3
3 Correct 38 ms 67540 KB n=3
4 Correct 40 ms 67520 KB n=4
5 Correct 40 ms 67480 KB n=4
6 Correct 39 ms 67584 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 67528 KB n=4
2 Correct 38 ms 67504 KB n=3
3 Correct 38 ms 67540 KB n=3
4 Correct 40 ms 67520 KB n=4
5 Correct 40 ms 67480 KB n=4
6 Correct 39 ms 67584 KB n=2
7 Correct 39 ms 67596 KB n=5
8 Correct 38 ms 67612 KB n=8
9 Correct 39 ms 67560 KB n=14
10 Correct 38 ms 67544 KB n=11
11 Correct 61 ms 71000 KB n=50000
12 Correct 62 ms 70848 KB n=50000
13 Correct 47 ms 67592 KB n=10
14 Correct 40 ms 67564 KB n=685
15 Correct 39 ms 67580 KB n=623
16 Correct 41 ms 67660 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 67528 KB n=4
2 Correct 38 ms 67504 KB n=3
3 Correct 38 ms 67540 KB n=3
4 Correct 40 ms 67520 KB n=4
5 Correct 40 ms 67480 KB n=4
6 Correct 39 ms 67584 KB n=2
7 Correct 39 ms 67596 KB n=5
8 Correct 38 ms 67612 KB n=8
9 Correct 39 ms 67560 KB n=14
10 Correct 38 ms 67544 KB n=11
11 Correct 61 ms 71000 KB n=50000
12 Correct 62 ms 70848 KB n=50000
13 Correct 47 ms 67592 KB n=10
14 Correct 40 ms 67564 KB n=685
15 Correct 39 ms 67580 KB n=623
16 Correct 41 ms 67660 KB n=973
17 Correct 40 ms 67648 KB n=989
18 Correct 42 ms 67672 KB n=563
19 Correct 46 ms 67780 KB n=592
20 Correct 40 ms 67780 KB n=938
21 Correct 38 ms 67716 KB n=747
22 Correct 43 ms 67780 KB n=991

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 118208 KB n=1000000
2 Correct 515 ms 97184 KB n=666666
3 Correct 316 ms 83388 KB n=400000
4 Correct 433 ms 116532 KB n=285714
5 Correct 59 ms 68268 KB n=20000
6 Correct 386 ms 108896 KB n=181818
7 Correct 50 ms 67944 KB n=10000
8 Correct 76 ms 71968 KB n=6666
9 Correct 41 ms 67616 KB n=4000
10 Correct 210 ms 92688 KB n=2857
11 Correct 41 ms 67648 KB n=2000

Subtask #5
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 67528 KB n=4
2 Correct 38 ms 67504 KB n=3
3 Correct 38 ms 67540 KB n=3
4 Correct 40 ms 67520 KB n=4
5 Correct 40 ms 67480 KB n=4
6 Correct 39 ms 67584 KB n=2
7 Correct 39 ms 67596 KB n=5
8 Correct 38 ms 67612 KB n=8
9 Correct 39 ms 67560 KB n=14
10 Correct 38 ms 67544 KB n=11
11 Correct 61 ms 71000 KB n=50000
12 Correct 62 ms 70848 KB n=50000
13 Correct 47 ms 67592 KB n=10
14 Correct 40 ms 67564 KB n=685
15 Correct 39 ms 67580 KB n=623
16 Correct 41 ms 67660 KB n=973
17 Correct 40 ms 67648 KB n=989
18 Correct 42 ms 67672 KB n=563
19 Correct 46 ms 67780 KB n=592
20 Correct 40 ms 67780 KB n=938
21 Correct 38 ms 67716 KB n=747
22 Correct 43 ms 67780 KB n=991
23 Correct 765 ms 118208 KB n=1000000
24 Correct 515 ms 97184 KB n=666666
25 Correct 316 ms 83388 KB n=400000
26 Correct 433 ms 116532 KB n=285714
27 Correct 59 ms 68268 KB n=20000
28 Correct 386 ms 108896 KB n=181818
29 Correct 50 ms 67944 KB n=10000
30 Correct 76 ms 71968 KB n=6666
31 Correct 41 ms 67616 KB n=4000
32 Correct 210 ms 92688 KB n=2857
33 Correct 41 ms 67648 KB n=2000
34 Correct 55 ms 69480 KB n=23514
35 Correct 66 ms 69448 KB n=23514
36 Correct 41 ms 67588 KB n=940
37 Correct 39 ms 67524 KB n=2
38 Correct 126 ms 80492 KB n=100000
39 Correct 126 ms 80308 KB n=100000
40 Correct 40 ms 67608 KB n=10
41 Correct 44 ms 67604 KB n=100
42 Correct 48 ms 68128 KB n=1000
43 Correct 747 ms 152736 KB n=1000000
44 Correct 905 ms 156920 KB n=1000000
45 Correct 722 ms 141512 KB n=666666
46 Correct 496 ms 123452 KB n=400000
47 Correct 249 ms 92532 KB n=2336
48 Correct 438 ms 116564 KB n=285714
49 Correct 395 ms 108804 KB n=181818
50 Correct 252 ms 97040 KB n=40000
51 Correct 230 ms 95328 KB n=20000
52 Correct 223 ms 93652 KB n=10000
53 Correct 232 ms 93292 KB n=6666
54 Correct 211 ms 92800 KB n=4000
55 Correct 246 ms 92720 KB n=2857
56 Correct 221 ms 91816 KB n=2000