oj.uz

Submission #496128

# Submission time Handle Problem Language Result Execution time Memory
496128 2021-12-20T18:15:40 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 50840 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>
 
using namespace std;
 
const long long oo = 1000000000000000000;
 
long long int  sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    freopen ( "sum.in", "r", stdin )
*/
 
int n, m, p[ 400001 ], used[ 400001 ], nn[ 400001 ], mm[ 400001 ];
vector <int> v[ 400001 ], ts, vv;
 
void dfs( int u ) {
	used[ u ] = 1;
	for ( int i = 1; i <= 2; i ++ ) {
		int to;
		if ( i == 1 ) {
			if ( nn[ u ] >= 0 )
				to = nn[ u ];
			else
				continue;
		}
		else {
			if ( mm[ u ] >= 0 )
				to = mm[ u ];
			else
				continue;
		}
		if ( !used[ to ] )
			dfs( to );
		else if ( used[ to ] == 1 ) {
			ans = 1;
			return;
		}
	}
	ts.push_back( u );
	used[ u ] = 2;
}
 
bool ok( int x ) {
	for ( int i = 0; i <= x; i ++ ) {
		used[ i ] = 0;
		p[ i ] = 0;
		nn[ i ] = -1;
		mm[ i ] = -1; 
	}
	for ( int i = n; i <= x; i ++ ) {
		nn[ i - n ] = i;
	}
	for ( int i = m; i <= x; i ++ ) {
		mm[ i ] = i - m;
	}
	ts.clear();
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
		if ( ans )
			return false;
	if ( sum ) {
		num = 0;
		for ( auto i : ts )
			p[ i ] = ++num;
		for ( int i = 1; i <= x; i ++ ) {
			p[ i ] -= p[ 0 ];
		}
		p[ 0 ] = 0;
	}
	return true;
}
 
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	int l, r, mid;
	while ( t -- ) {
		cin >> n >> m;
		mx = max( n, m );
		l = mx - 1;
		r = 400000;
		sum = 0;
		while ( r - l > 1 ) {
			mid = ( r + l ) / 2;
			if ( ok( mid ) )
				l = mid;
			else
				r = mid - 1;
		}
		if ( ok( r ) ) {
			sum = 1;
			ok( r );
			cout << r << "\n";
			for ( int i = 1; i <= r; i ++ )
				cout << p[ i ] - p[ i - 1 ] << " ";
		}
		else {
			sum = 1;
			ok( l );
			cout << l << "\n";
			for ( int i = 1; i <= l; i ++ )
				cout << p[ i ] - p[ i - 1 ] << " ";
		}
		cout << "\n";
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20172 KB Ok
2 Correct 56 ms 19912 KB Ok
3 Correct 63 ms 14224 KB Ok
4 Correct 41 ms 13872 KB Ok
5 Correct 46 ms 14412 KB Ok
6 Correct 41 ms 15104 KB Ok
7 Correct 43 ms 14312 KB Ok
8 Correct 56 ms 15476 KB Ok
9 Correct 52 ms 14028 KB Ok
10 Correct 42 ms 16496 KB Ok
11 Correct 39 ms 13808 KB Ok
12 Correct 39 ms 13004 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17088 KB Ok
2 Correct 48 ms 16876 KB Ok
3 Correct 49 ms 17152 KB Ok
4 Correct 51 ms 16872 KB Ok
5 Correct 51 ms 17144 KB Ok
6 Correct 52 ms 17216 KB Ok
7 Correct 68 ms 17568 KB Ok
8 Correct 66 ms 17348 KB Ok
9 Correct 76 ms 17660 KB Ok
10 Correct 61 ms 17272 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19788 KB Ok
2 Correct 49 ms 19944 KB Ok
3 Correct 47 ms 16748 KB Ok
4 Correct 50 ms 16124 KB Ok
5 Correct 45 ms 20176 KB Ok
6 Correct 49 ms 19888 KB Ok
7 Correct 48 ms 20292 KB Ok
8 Correct 48 ms 19912 KB Ok
9 Correct 48 ms 19860 KB Ok
10 Correct 49 ms 16792 KB Ok
11 Correct 53 ms 15688 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 17140 KB Ok
2 Correct 58 ms 14704 KB Ok
3 Correct 56 ms 14448 KB Ok
4 Correct 52 ms 14284 KB Ok
5 Correct 55 ms 14196 KB Ok
6 Correct 327 ms 22872 KB Ok
7 Correct 302 ms 23056 KB Ok
8 Correct 543 ms 25920 KB Ok
9 Correct 381 ms 24432 KB Ok
10 Correct 249 ms 18792 KB Ok
11 Correct 355 ms 24432 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20172 KB Ok
2 Correct 56 ms 19912 KB Ok
3 Correct 63 ms 14224 KB Ok
4 Correct 41 ms 13872 KB Ok
5 Correct 46 ms 14412 KB Ok
6 Correct 41 ms 15104 KB Ok
7 Correct 43 ms 14312 KB Ok
8 Correct 56 ms 15476 KB Ok
9 Correct 52 ms 14028 KB Ok
10 Correct 42 ms 16496 KB Ok
11 Correct 39 ms 13808 KB Ok
12 Correct 39 ms 13004 KB Ok
13 Correct 27 ms 19788 KB Ok
14 Correct 49 ms 19944 KB Ok
15 Correct 47 ms 16748 KB Ok
16 Correct 50 ms 16124 KB Ok
17 Correct 45 ms 20176 KB Ok
18 Correct 49 ms 19888 KB Ok
19 Correct 48 ms 20292 KB Ok
20 Correct 48 ms 19912 KB Ok
21 Correct 48 ms 19860 KB Ok
22 Correct 49 ms 16792 KB Ok
23 Correct 53 ms 15688 KB Ok
24 Correct 62 ms 14032 KB Ok
25 Correct 54 ms 13944 KB Ok
26 Correct 50 ms 14028 KB Ok
27 Correct 54 ms 14028 KB Ok
28 Correct 51 ms 14024 KB Ok
29 Correct 47 ms 14064 KB Ok
30 Correct 64 ms 14028 KB Ok
31 Correct 56 ms 14028 KB Ok
32 Correct 49 ms 13984 KB Ok
33 Correct 51 ms 14028 KB Ok
34 Correct 91 ms 14076 KB Ok
35 Correct 76 ms 14052 KB Ok
36 Correct 99 ms 14072 KB Ok
37 Correct 76 ms 14028 KB Ok
38 Correct 68 ms 14028 KB Ok
39 Correct 71 ms 14076 KB Ok
40 Correct 75 ms 14060 KB Ok
41 Correct 78 ms 14060 KB Ok
42 Correct 95 ms 14156 KB Ok
43 Correct 79 ms 14064 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20172 KB Ok
2 Correct 56 ms 19912 KB Ok
3 Correct 63 ms 14224 KB Ok
4 Correct 41 ms 13872 KB Ok
5 Correct 46 ms 14412 KB Ok
6 Correct 41 ms 15104 KB Ok
7 Correct 43 ms 14312 KB Ok
8 Correct 56 ms 15476 KB Ok
9 Correct 52 ms 14028 KB Ok
10 Correct 42 ms 16496 KB Ok
11 Correct 39 ms 13808 KB Ok
12 Correct 39 ms 13004 KB Ok
13 Correct 47 ms 17088 KB Ok
14 Correct 48 ms 16876 KB Ok
15 Correct 49 ms 17152 KB Ok
16 Correct 51 ms 16872 KB Ok
17 Correct 51 ms 17144 KB Ok
18 Correct 52 ms 17216 KB Ok
19 Correct 68 ms 17568 KB Ok
20 Correct 66 ms 17348 KB Ok
21 Correct 76 ms 17660 KB Ok
22 Correct 61 ms 17272 KB Ok
23 Correct 27 ms 19788 KB Ok
24 Correct 49 ms 19944 KB Ok
25 Correct 47 ms 16748 KB Ok
26 Correct 50 ms 16124 KB Ok
27 Correct 45 ms 20176 KB Ok
28 Correct 49 ms 19888 KB Ok
29 Correct 48 ms 20292 KB Ok
30 Correct 48 ms 19912 KB Ok
31 Correct 48 ms 19860 KB Ok
32 Correct 49 ms 16792 KB Ok
33 Correct 53 ms 15688 KB Ok
34 Correct 62 ms 14032 KB Ok
35 Correct 54 ms 13944 KB Ok
36 Correct 50 ms 14028 KB Ok
37 Correct 54 ms 14028 KB Ok
38 Correct 51 ms 14024 KB Ok
39 Correct 47 ms 14064 KB Ok
40 Correct 64 ms 14028 KB Ok
41 Correct 56 ms 14028 KB Ok
42 Correct 49 ms 13984 KB Ok
43 Correct 51 ms 14028 KB Ok
44 Correct 91 ms 14076 KB Ok
45 Correct 76 ms 14052 KB Ok
46 Correct 99 ms 14072 KB Ok
47 Correct 76 ms 14028 KB Ok
48 Correct 68 ms 14028 KB Ok
49 Correct 71 ms 14076 KB Ok
50 Correct 75 ms 14060 KB Ok
51 Correct 78 ms 14060 KB Ok
52 Correct 95 ms 14156 KB Ok
53 Correct 79 ms 14064 KB Ok
54 Correct 235 ms 15844 KB Ok
55 Correct 295 ms 16308 KB Ok
56 Correct 283 ms 16104 KB Ok
57 Correct 185 ms 15548 KB Ok
58 Correct 246 ms 15712 KB Ok
59 Correct 216 ms 15472 KB Ok
60 Correct 206 ms 15332 KB Ok
61 Correct 195 ms 15420 KB Ok
62 Correct 280 ms 15996 KB Ok
63 Correct 229 ms 15600 KB Ok
64 Correct 272 ms 16252 KB Ok
65 Correct 271 ms 15840 KB Ok
66 Correct 231 ms 15752 KB Ok
67 Correct 219 ms 15520 KB Ok
68 Correct 221 ms 15740 KB Ok
69 Correct 538 ms 23264 KB Ok
70 Correct 534 ms 24036 KB Ok
71 Correct 526 ms 23468 KB Ok
72 Correct 511 ms 23344 KB Ok
73 Correct 526 ms 23308 KB Ok
74 Correct 520 ms 23192 KB Ok
75 Correct 532 ms 22800 KB Ok
76 Correct 540 ms 23648 KB Ok
77 Correct 538 ms 22880 KB Ok
78 Correct 535 ms 23364 KB Ok
79 Correct 531 ms 23452 KB Ok
80 Correct 505 ms 23628 KB Ok
81 Correct 496 ms 23460 KB Ok
82 Correct 498 ms 23500 KB Ok
83 Correct 513 ms 22928 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 20172 KB Ok
2 Correct 56 ms 19912 KB Ok
3 Correct 63 ms 14224 KB Ok
4 Correct 41 ms 13872 KB Ok
5 Correct 46 ms 14412 KB Ok
6 Correct 41 ms 15104 KB Ok
7 Correct 43 ms 14312 KB Ok
8 Correct 56 ms 15476 KB Ok
9 Correct 52 ms 14028 KB Ok
10 Correct 42 ms 16496 KB Ok
11 Correct 39 ms 13808 KB Ok
12 Correct 39 ms 13004 KB Ok
13 Correct 47 ms 17088 KB Ok
14 Correct 48 ms 16876 KB Ok
15 Correct 49 ms 17152 KB Ok
16 Correct 51 ms 16872 KB Ok
17 Correct 51 ms 17144 KB Ok
18 Correct 52 ms 17216 KB Ok
19 Correct 68 ms 17568 KB Ok
20 Correct 66 ms 17348 KB Ok
21 Correct 76 ms 17660 KB Ok
22 Correct 61 ms 17272 KB Ok
23 Correct 27 ms 19788 KB Ok
24 Correct 49 ms 19944 KB Ok
25 Correct 47 ms 16748 KB Ok
26 Correct 50 ms 16124 KB Ok
27 Correct 45 ms 20176 KB Ok
28 Correct 49 ms 19888 KB Ok
29 Correct 48 ms 20292 KB Ok
30 Correct 48 ms 19912 KB Ok
31 Correct 48 ms 19860 KB Ok
32 Correct 49 ms 16792 KB Ok
33 Correct 53 ms 15688 KB Ok
34 Correct 50 ms 17140 KB Ok
35 Correct 58 ms 14704 KB Ok
36 Correct 56 ms 14448 KB Ok
37 Correct 52 ms 14284 KB Ok
38 Correct 55 ms 14196 KB Ok
39 Correct 327 ms 22872 KB Ok
40 Correct 302 ms 23056 KB Ok
41 Correct 543 ms 25920 KB Ok
42 Correct 381 ms 24432 KB Ok
43 Correct 249 ms 18792 KB Ok
44 Correct 355 ms 24432 KB Ok
45 Correct 62 ms 14032 KB Ok
46 Correct 54 ms 13944 KB Ok
47 Correct 50 ms 14028 KB Ok
48 Correct 54 ms 14028 KB Ok
49 Correct 51 ms 14024 KB Ok
50 Correct 47 ms 14064 KB Ok
51 Correct 64 ms 14028 KB Ok
52 Correct 56 ms 14028 KB Ok
53 Correct 49 ms 13984 KB Ok
54 Correct 51 ms 14028 KB Ok
55 Correct 91 ms 14076 KB Ok
56 Correct 76 ms 14052 KB Ok
57 Correct 99 ms 14072 KB Ok
58 Correct 76 ms 14028 KB Ok
59 Correct 68 ms 14028 KB Ok
60 Correct 71 ms 14076 KB Ok
61 Correct 75 ms 14060 KB Ok
62 Correct 78 ms 14060 KB Ok
63 Correct 95 ms 14156 KB Ok
64 Correct 79 ms 14064 KB Ok
65 Correct 235 ms 15844 KB Ok
66 Correct 295 ms 16308 KB Ok
67 Correct 283 ms 16104 KB Ok
68 Correct 185 ms 15548 KB Ok
69 Correct 246 ms 15712 KB Ok
70 Correct 216 ms 15472 KB Ok
71 Correct 206 ms 15332 KB Ok
72 Correct 195 ms 15420 KB Ok
73 Correct 280 ms 15996 KB Ok
74 Correct 229 ms 15600 KB Ok
75 Correct 272 ms 16252 KB Ok
76 Correct 271 ms 15840 KB Ok
77 Correct 231 ms 15752 KB Ok
78 Correct 219 ms 15520 KB Ok
79 Correct 221 ms 15740 KB Ok
80 Correct 538 ms 23264 KB Ok
81 Correct 534 ms 24036 KB Ok
82 Correct 526 ms 23468 KB Ok
83 Correct 511 ms 23344 KB Ok
84 Correct 526 ms 23308 KB Ok
85 Correct 520 ms 23192 KB Ok
86 Correct 532 ms 22800 KB Ok
87 Correct 540 ms 23648 KB Ok
88 Correct 538 ms 22880 KB Ok
89 Correct 535 ms 23364 KB Ok
90 Correct 531 ms 23452 KB Ok
91 Correct 505 ms 23628 KB Ok
92 Correct 496 ms 23460 KB Ok
93 Correct 498 ms 23500 KB Ok
94 Correct 513 ms 22928 KB Ok
95 Correct 513 ms 19808 KB Ok
96 Correct 785 ms 22716 KB Ok
97 Correct 680 ms 20724 KB Ok
98 Correct 485 ms 20560 KB Ok
99 Correct 647 ms 20364 KB Ok
100 Correct 643 ms 20612 KB Ok
101 Correct 659 ms 21376 KB Ok
102 Correct 674 ms 20548 KB Ok
103 Correct 609 ms 21476 KB Ok
104 Correct 743 ms 22564 KB Ok
105 Correct 754 ms 22568 KB Ok
106 Correct 587 ms 22352 KB Ok
107 Correct 755 ms 21976 KB Ok
108 Correct 783 ms 22604 KB Ok
109 Correct 685 ms 22956 KB Ok
110 Execution timed out 2071 ms 50840 KB Time limit exceeded
111 Halted 0 ms 0 KB -