oj.uz

Submission #496583

# Submission time Handle Problem Language Result Execution time Memory
496583 2021-12-21T14:58:18 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++11
100 / 100
 1922 ms 47544 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 sz;
int n, m, p[ 400001 ], used[ 400001 ], nn[ 400001 ], mm[ 400001 ], ts[400001];
vector <int> vv;
 
inline void dfs( int u ) {
	used[ u ] = 1;
	for ( int i = 1; i <= 2; i ++ ) {
		int to;
		if ( ans )
			return;
		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;
		}
	}
		if ( ans )
			return;
	used[ u ] = 2;
}
 
inline void dfs1( 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 ] )
			dfs1( to );
	}
	ts[sz++] = u ;
}
 
bool ok( int x ) {
	for ( int i = 0; i <= x; i ++ ) {
		used[ i ] = 0;
		nn[ i ] = -1;
		mm[ i ] = -1; 
		if ( i >= n )
			nn[ i - n ] = i;
		if ( i >= m )
			mm[ i ] = i - m; 
	}
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	if ( sum ) {
		sz = 0;
		for ( int i = 0; i <= x; i ++ ) {
			p[ i ] = 0;
			used[ i ] = 0;
		}
		for ( int i = 0; i<= x; i ++ ) {
			if ( !used[ i ] )
				dfs1( i );
		}
		num = 0;
        for (int j = 0; j < sz; j++) {
          int i = ts[j];
          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 34 ms 8000 KB Ok
2 Correct 38 ms 7884 KB Ok
3 Correct 46 ms 2996 KB Ok
4 Correct 13 ms 3008 KB Ok
5 Correct 14 ms 3020 KB Ok
6 Correct 13 ms 3916 KB Ok
7 Correct 14 ms 2944 KB Ok
8 Correct 20 ms 3884 KB Ok
9 Correct 15 ms 2836 KB Ok
10 Correct 17 ms 5184 KB Ok
11 Correct 22 ms 2936 KB Ok
12 Correct 14 ms 2848 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5184 KB Ok
2 Correct 49 ms 5276 KB Ok
3 Correct 32 ms 5196 KB Ok
4 Correct 18 ms 5292 KB Ok
5 Correct 25 ms 5196 KB Ok
6 Correct 38 ms 5360 KB Ok
7 Correct 38 ms 5892 KB Ok
8 Correct 35 ms 5516 KB Ok
9 Correct 38 ms 5988 KB Ok
10 Correct 33 ms 5716 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7876 KB Ok
2 Correct 31 ms 7872 KB Ok
3 Correct 25 ms 5264 KB Ok
4 Correct 21 ms 4424 KB Ok
5 Correct 18 ms 7872 KB Ok
6 Correct 19 ms 7888 KB Ok
7 Correct 18 ms 7900 KB Ok
8 Correct 46 ms 7804 KB Ok
9 Correct 19 ms 7876 KB Ok
10 Correct 24 ms 5196 KB Ok
11 Correct 17 ms 4368 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5292 KB Ok
2 Correct 14 ms 3408 KB Ok
3 Correct 13 ms 3088 KB Ok
4 Correct 13 ms 3000 KB Ok
5 Correct 12 ms 2920 KB Ok
6 Correct 250 ms 11752 KB Ok
7 Correct 192 ms 12316 KB Ok
8 Correct 364 ms 15284 KB Ok
9 Correct 257 ms 13668 KB Ok
10 Correct 137 ms 7880 KB Ok
11 Correct 242 ms 13380 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8000 KB Ok
2 Correct 38 ms 7884 KB Ok
3 Correct 46 ms 2996 KB Ok
4 Correct 13 ms 3008 KB Ok
5 Correct 14 ms 3020 KB Ok
6 Correct 13 ms 3916 KB Ok
7 Correct 14 ms 2944 KB Ok
8 Correct 20 ms 3884 KB Ok
9 Correct 15 ms 2836 KB Ok
10 Correct 17 ms 5184 KB Ok
11 Correct 22 ms 2936 KB Ok
12 Correct 14 ms 2848 KB Ok
13 Correct 11 ms 7876 KB Ok
14 Correct 31 ms 7872 KB Ok
15 Correct 25 ms 5264 KB Ok
16 Correct 21 ms 4424 KB Ok
17 Correct 18 ms 7872 KB Ok
18 Correct 19 ms 7888 KB Ok
19 Correct 18 ms 7900 KB Ok
20 Correct 46 ms 7804 KB Ok
21 Correct 19 ms 7876 KB Ok
22 Correct 24 ms 5196 KB Ok
23 Correct 17 ms 4368 KB Ok
24 Correct 15 ms 2768 KB Ok
25 Correct 15 ms 2740 KB Ok
26 Correct 14 ms 2748 KB Ok
27 Correct 42 ms 2696 KB Ok
28 Correct 14 ms 2756 KB Ok
29 Correct 20 ms 2752 KB Ok
30 Correct 19 ms 2720 KB Ok
31 Correct 44 ms 2748 KB Ok
32 Correct 43 ms 2744 KB Ok
33 Correct 16 ms 2740 KB Ok
34 Correct 18 ms 2880 KB Ok
35 Correct 19 ms 2892 KB Ok
36 Correct 20 ms 2892 KB Ok
37 Correct 19 ms 2904 KB Ok
38 Correct 54 ms 2944 KB Ok
39 Correct 18 ms 2876 KB Ok
40 Correct 20 ms 2884 KB Ok
41 Correct 21 ms 2884 KB Ok
42 Correct 38 ms 2860 KB Ok
43 Correct 21 ms 2888 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8000 KB Ok
2 Correct 38 ms 7884 KB Ok
3 Correct 46 ms 2996 KB Ok
4 Correct 13 ms 3008 KB Ok
5 Correct 14 ms 3020 KB Ok
6 Correct 13 ms 3916 KB Ok
7 Correct 14 ms 2944 KB Ok
8 Correct 20 ms 3884 KB Ok
9 Correct 15 ms 2836 KB Ok
10 Correct 17 ms 5184 KB Ok
11 Correct 22 ms 2936 KB Ok
12 Correct 14 ms 2848 KB Ok
13 Correct 21 ms 5184 KB Ok
14 Correct 49 ms 5276 KB Ok
15 Correct 32 ms 5196 KB Ok
16 Correct 18 ms 5292 KB Ok
17 Correct 25 ms 5196 KB Ok
18 Correct 38 ms 5360 KB Ok
19 Correct 38 ms 5892 KB Ok
20 Correct 35 ms 5516 KB Ok
21 Correct 38 ms 5988 KB Ok
22 Correct 33 ms 5716 KB Ok
23 Correct 11 ms 7876 KB Ok
24 Correct 31 ms 7872 KB Ok
25 Correct 25 ms 5264 KB Ok
26 Correct 21 ms 4424 KB Ok
27 Correct 18 ms 7872 KB Ok
28 Correct 19 ms 7888 KB Ok
29 Correct 18 ms 7900 KB Ok
30 Correct 46 ms 7804 KB Ok
31 Correct 19 ms 7876 KB Ok
32 Correct 24 ms 5196 KB Ok
33 Correct 17 ms 4368 KB Ok
34 Correct 15 ms 2768 KB Ok
35 Correct 15 ms 2740 KB Ok
36 Correct 14 ms 2748 KB Ok
37 Correct 42 ms 2696 KB Ok
38 Correct 14 ms 2756 KB Ok
39 Correct 20 ms 2752 KB Ok
40 Correct 19 ms 2720 KB Ok
41 Correct 44 ms 2748 KB Ok
42 Correct 43 ms 2744 KB Ok
43 Correct 16 ms 2740 KB Ok
44 Correct 18 ms 2880 KB Ok
45 Correct 19 ms 2892 KB Ok
46 Correct 20 ms 2892 KB Ok
47 Correct 19 ms 2904 KB Ok
48 Correct 54 ms 2944 KB Ok
49 Correct 18 ms 2876 KB Ok
50 Correct 20 ms 2884 KB Ok
51 Correct 21 ms 2884 KB Ok
52 Correct 38 ms 2860 KB Ok
53 Correct 21 ms 2888 KB Ok
54 Correct 124 ms 5360 KB Ok
55 Correct 146 ms 5636 KB Ok
56 Correct 196 ms 5688 KB Ok
57 Correct 154 ms 4896 KB Ok
58 Correct 115 ms 5064 KB Ok
59 Correct 107 ms 4924 KB Ok
60 Correct 96 ms 4736 KB Ok
61 Correct 108 ms 4932 KB Ok
62 Correct 291 ms 5464 KB Ok
63 Correct 122 ms 5020 KB Ok
64 Correct 135 ms 5620 KB Ok
65 Correct 145 ms 5400 KB Ok
66 Correct 110 ms 5084 KB Ok
67 Correct 101 ms 5020 KB Ok
68 Correct 328 ms 5188 KB Ok
69 Correct 333 ms 12368 KB Ok
70 Correct 417 ms 12956 KB Ok
71 Correct 332 ms 12360 KB Ok
72 Correct 358 ms 12252 KB Ok
73 Correct 340 ms 12316 KB Ok
74 Correct 340 ms 12096 KB Ok
75 Correct 326 ms 11728 KB Ok
76 Correct 396 ms 12480 KB Ok
77 Correct 291 ms 11836 KB Ok
78 Correct 367 ms 12308 KB Ok
79 Correct 338 ms 12536 KB Ok
80 Correct 347 ms 12548 KB Ok
81 Correct 358 ms 12388 KB Ok
82 Correct 322 ms 12372 KB Ok
83 Correct 306 ms 11828 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8000 KB Ok
2 Correct 38 ms 7884 KB Ok
3 Correct 46 ms 2996 KB Ok
4 Correct 13 ms 3008 KB Ok
5 Correct 14 ms 3020 KB Ok
6 Correct 13 ms 3916 KB Ok
7 Correct 14 ms 2944 KB Ok
8 Correct 20 ms 3884 KB Ok
9 Correct 15 ms 2836 KB Ok
10 Correct 17 ms 5184 KB Ok
11 Correct 22 ms 2936 KB Ok
12 Correct 14 ms 2848 KB Ok
13 Correct 21 ms 5184 KB Ok
14 Correct 49 ms 5276 KB Ok
15 Correct 32 ms 5196 KB Ok
16 Correct 18 ms 5292 KB Ok
17 Correct 25 ms 5196 KB Ok
18 Correct 38 ms 5360 KB Ok
19 Correct 38 ms 5892 KB Ok
20 Correct 35 ms 5516 KB Ok
21 Correct 38 ms 5988 KB Ok
22 Correct 33 ms 5716 KB Ok
23 Correct 11 ms 7876 KB Ok
24 Correct 31 ms 7872 KB Ok
25 Correct 25 ms 5264 KB Ok
26 Correct 21 ms 4424 KB Ok
27 Correct 18 ms 7872 KB Ok
28 Correct 19 ms 7888 KB Ok
29 Correct 18 ms 7900 KB Ok
30 Correct 46 ms 7804 KB Ok
31 Correct 19 ms 7876 KB Ok
32 Correct 24 ms 5196 KB Ok
33 Correct 17 ms 4368 KB Ok
34 Correct 30 ms 5292 KB Ok
35 Correct 14 ms 3408 KB Ok
36 Correct 13 ms 3088 KB Ok
37 Correct 13 ms 3000 KB Ok
38 Correct 12 ms 2920 KB Ok
39 Correct 250 ms 11752 KB Ok
40 Correct 192 ms 12316 KB Ok
41 Correct 364 ms 15284 KB Ok
42 Correct 257 ms 13668 KB Ok
43 Correct 137 ms 7880 KB Ok
44 Correct 242 ms 13380 KB Ok
45 Correct 15 ms 2768 KB Ok
46 Correct 15 ms 2740 KB Ok
47 Correct 14 ms 2748 KB Ok
48 Correct 42 ms 2696 KB Ok
49 Correct 14 ms 2756 KB Ok
50 Correct 20 ms 2752 KB Ok
51 Correct 19 ms 2720 KB Ok
52 Correct 44 ms 2748 KB Ok
53 Correct 43 ms 2744 KB Ok
54 Correct 16 ms 2740 KB Ok
55 Correct 18 ms 2880 KB Ok
56 Correct 19 ms 2892 KB Ok
57 Correct 20 ms 2892 KB Ok
58 Correct 19 ms 2904 KB Ok
59 Correct 54 ms 2944 KB Ok
60 Correct 18 ms 2876 KB Ok
61 Correct 20 ms 2884 KB Ok
62 Correct 21 ms 2884 KB Ok
63 Correct 38 ms 2860 KB Ok
64 Correct 21 ms 2888 KB Ok
65 Correct 124 ms 5360 KB Ok
66 Correct 146 ms 5636 KB Ok
67 Correct 196 ms 5688 KB Ok
68 Correct 154 ms 4896 KB Ok
69 Correct 115 ms 5064 KB Ok
70 Correct 107 ms 4924 KB Ok
71 Correct 96 ms 4736 KB Ok
72 Correct 108 ms 4932 KB Ok
73 Correct 291 ms 5464 KB Ok
74 Correct 122 ms 5020 KB Ok
75 Correct 135 ms 5620 KB Ok
76 Correct 145 ms 5400 KB Ok
77 Correct 110 ms 5084 KB Ok
78 Correct 101 ms 5020 KB Ok
79 Correct 328 ms 5188 KB Ok
80 Correct 333 ms 12368 KB Ok
81 Correct 417 ms 12956 KB Ok
82 Correct 332 ms 12360 KB Ok
83 Correct 358 ms 12252 KB Ok
84 Correct 340 ms 12316 KB Ok
85 Correct 340 ms 12096 KB Ok
86 Correct 326 ms 11728 KB Ok
87 Correct 396 ms 12480 KB Ok
88 Correct 291 ms 11836 KB Ok
89 Correct 367 ms 12308 KB Ok
90 Correct 338 ms 12536 KB Ok
91 Correct 347 ms 12548 KB Ok
92 Correct 358 ms 12388 KB Ok
93 Correct 322 ms 12372 KB Ok
94 Correct 306 ms 11828 KB Ok
95 Correct 284 ms 9980 KB Ok
96 Correct 394 ms 13116 KB Ok
97 Correct 372 ms 11112 KB Ok
98 Correct 286 ms 10776 KB Ok
99 Correct 312 ms 10524 KB Ok
100 Correct 371 ms 10732 KB Ok
101 Correct 382 ms 11800 KB Ok
102 Correct 388 ms 10952 KB Ok
103 Correct 328 ms 11688 KB Ok
104 Correct 394 ms 13012 KB Ok
105 Correct 367 ms 12944 KB Ok
106 Correct 309 ms 12740 KB Ok
107 Correct 357 ms 12280 KB Ok
108 Correct 439 ms 12992 KB Ok
109 Correct 451 ms 13320 KB Ok
110 Correct 1582 ms 43504 KB Ok
111 Correct 1922 ms 46280 KB Ok
112 Correct 1734 ms 46336 KB Ok
113 Correct 1626 ms 45644 KB Ok
114 Correct 1602 ms 47544 KB Ok
115 Correct 1803 ms 45296 KB Ok
116 Correct 1707 ms 46676 KB Ok
117 Correct 1876 ms 45072 KB Ok
118 Correct 1530 ms 45208 KB Ok
119 Correct 1849 ms 45184 KB Ok
120 Correct 1767 ms 44876 KB Ok
121 Correct 1625 ms 43824 KB Ok
122 Correct 1667 ms 46104 KB Ok
123 Correct 1791 ms 46380 KB Ok
124 Correct 1507 ms 43832 KB Ok
125 Correct 960 ms 29044 KB Ok