oj.uz

Submission #496129

# Submission time Handle Problem Language Result Execution time Memory
496129 2021-12-20T18:18:17 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 52740 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;
		}
	}
	used[ u ] = 2;
}

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.push_back( u );
}
 
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;
	}
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
		if ( ans )
			return false;
	if ( sum ) {
		ts.clear();
		for ( int i = 0; i <= x; i ++ )
			used[ i ] = 0;
		for ( int i = 0; i<= x; i ++ ) {
			if ( !used[ i ] )
				dfs1( i );
		}
		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 42 ms 19092 KB Ok
2 Correct 43 ms 19104 KB Ok
3 Correct 47 ms 13208 KB Ok
4 Correct 40 ms 13288 KB Ok
5 Correct 37 ms 13260 KB Ok
6 Correct 50 ms 14412 KB Ok
7 Correct 41 ms 13272 KB Ok
8 Correct 39 ms 14416 KB Ok
9 Correct 42 ms 12996 KB Ok
10 Correct 39 ms 15904 KB Ok
11 Correct 41 ms 13160 KB Ok
12 Correct 59 ms 13028 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15936 KB Ok
2 Correct 40 ms 15948 KB Ok
3 Correct 43 ms 15980 KB Ok
4 Correct 39 ms 15948 KB Ok
5 Correct 40 ms 15948 KB Ok
6 Correct 45 ms 16088 KB Ok
7 Correct 71 ms 16640 KB Ok
8 Correct 56 ms 16276 KB Ok
9 Correct 62 ms 16772 KB Ok
10 Correct 50 ms 16444 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19020 KB Ok
2 Correct 47 ms 19100 KB Ok
3 Correct 43 ms 15932 KB Ok
4 Correct 39 ms 14940 KB Ok
5 Correct 48 ms 19100 KB Ok
6 Correct 44 ms 19012 KB Ok
7 Correct 40 ms 19108 KB Ok
8 Correct 40 ms 19020 KB Ok
9 Correct 40 ms 19128 KB Ok
10 Correct 39 ms 15956 KB Ok
11 Correct 42 ms 14924 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15964 KB Ok
2 Correct 45 ms 13644 KB Ok
3 Correct 38 ms 13260 KB Ok
4 Correct 37 ms 13132 KB Ok
5 Correct 40 ms 13076 KB Ok
6 Correct 266 ms 22428 KB Ok
7 Correct 247 ms 22768 KB Ok
8 Correct 464 ms 25768 KB Ok
9 Correct 327 ms 24184 KB Ok
10 Correct 211 ms 18308 KB Ok
11 Correct 268 ms 24204 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19092 KB Ok
2 Correct 43 ms 19104 KB Ok
3 Correct 47 ms 13208 KB Ok
4 Correct 40 ms 13288 KB Ok
5 Correct 37 ms 13260 KB Ok
6 Correct 50 ms 14412 KB Ok
7 Correct 41 ms 13272 KB Ok
8 Correct 39 ms 14416 KB Ok
9 Correct 42 ms 12996 KB Ok
10 Correct 39 ms 15904 KB Ok
11 Correct 41 ms 13160 KB Ok
12 Correct 59 ms 13028 KB Ok
13 Correct 23 ms 19020 KB Ok
14 Correct 47 ms 19100 KB Ok
15 Correct 43 ms 15932 KB Ok
16 Correct 39 ms 14940 KB Ok
17 Correct 48 ms 19100 KB Ok
18 Correct 44 ms 19012 KB Ok
19 Correct 40 ms 19108 KB Ok
20 Correct 40 ms 19020 KB Ok
21 Correct 40 ms 19128 KB Ok
22 Correct 39 ms 15956 KB Ok
23 Correct 42 ms 14924 KB Ok
24 Correct 51 ms 12932 KB Ok
25 Correct 46 ms 12940 KB Ok
26 Correct 50 ms 13008 KB Ok
27 Correct 49 ms 12876 KB Ok
28 Correct 45 ms 12960 KB Ok
29 Correct 43 ms 12936 KB Ok
30 Correct 47 ms 12912 KB Ok
31 Correct 57 ms 12912 KB Ok
32 Correct 43 ms 12944 KB Ok
33 Correct 44 ms 12880 KB Ok
34 Correct 55 ms 13084 KB Ok
35 Correct 57 ms 13144 KB Ok
36 Correct 66 ms 13052 KB Ok
37 Correct 73 ms 13088 KB Ok
38 Correct 57 ms 13052 KB Ok
39 Correct 54 ms 13084 KB Ok
40 Correct 76 ms 13056 KB Ok
41 Correct 58 ms 13080 KB Ok
42 Correct 57 ms 13076 KB Ok
43 Correct 60 ms 13128 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19092 KB Ok
2 Correct 43 ms 19104 KB Ok
3 Correct 47 ms 13208 KB Ok
4 Correct 40 ms 13288 KB Ok
5 Correct 37 ms 13260 KB Ok
6 Correct 50 ms 14412 KB Ok
7 Correct 41 ms 13272 KB Ok
8 Correct 39 ms 14416 KB Ok
9 Correct 42 ms 12996 KB Ok
10 Correct 39 ms 15904 KB Ok
11 Correct 41 ms 13160 KB Ok
12 Correct 59 ms 13028 KB Ok
13 Correct 53 ms 15936 KB Ok
14 Correct 40 ms 15948 KB Ok
15 Correct 43 ms 15980 KB Ok
16 Correct 39 ms 15948 KB Ok
17 Correct 40 ms 15948 KB Ok
18 Correct 45 ms 16088 KB Ok
19 Correct 71 ms 16640 KB Ok
20 Correct 56 ms 16276 KB Ok
21 Correct 62 ms 16772 KB Ok
22 Correct 50 ms 16444 KB Ok
23 Correct 23 ms 19020 KB Ok
24 Correct 47 ms 19100 KB Ok
25 Correct 43 ms 15932 KB Ok
26 Correct 39 ms 14940 KB Ok
27 Correct 48 ms 19100 KB Ok
28 Correct 44 ms 19012 KB Ok
29 Correct 40 ms 19108 KB Ok
30 Correct 40 ms 19020 KB Ok
31 Correct 40 ms 19128 KB Ok
32 Correct 39 ms 15956 KB Ok
33 Correct 42 ms 14924 KB Ok
34 Correct 51 ms 12932 KB Ok
35 Correct 46 ms 12940 KB Ok
36 Correct 50 ms 13008 KB Ok
37 Correct 49 ms 12876 KB Ok
38 Correct 45 ms 12960 KB Ok
39 Correct 43 ms 12936 KB Ok
40 Correct 47 ms 12912 KB Ok
41 Correct 57 ms 12912 KB Ok
42 Correct 43 ms 12944 KB Ok
43 Correct 44 ms 12880 KB Ok
44 Correct 55 ms 13084 KB Ok
45 Correct 57 ms 13144 KB Ok
46 Correct 66 ms 13052 KB Ok
47 Correct 73 ms 13088 KB Ok
48 Correct 57 ms 13052 KB Ok
49 Correct 54 ms 13084 KB Ok
50 Correct 76 ms 13056 KB Ok
51 Correct 58 ms 13080 KB Ok
52 Correct 57 ms 13076 KB Ok
53 Correct 60 ms 13128 KB Ok
54 Correct 177 ms 15404 KB Ok
55 Correct 242 ms 15712 KB Ok
56 Correct 238 ms 15728 KB Ok
57 Correct 147 ms 14916 KB Ok
58 Correct 190 ms 15188 KB Ok
59 Correct 192 ms 14976 KB Ok
60 Correct 167 ms 14836 KB Ok
61 Correct 154 ms 15092 KB Ok
62 Correct 205 ms 15476 KB Ok
63 Correct 161 ms 15136 KB Ok
64 Correct 218 ms 15676 KB Ok
65 Correct 169 ms 15296 KB Ok
66 Correct 162 ms 15136 KB Ok
67 Correct 150 ms 15084 KB Ok
68 Correct 164 ms 15368 KB Ok
69 Correct 463 ms 22920 KB Ok
70 Correct 484 ms 23444 KB Ok
71 Correct 451 ms 22884 KB Ok
72 Correct 450 ms 22748 KB Ok
73 Correct 467 ms 22924 KB Ok
74 Correct 487 ms 22712 KB Ok
75 Correct 472 ms 22276 KB Ok
76 Correct 522 ms 23244 KB Ok
77 Correct 449 ms 22320 KB Ok
78 Correct 482 ms 22796 KB Ok
79 Correct 460 ms 23060 KB Ok
80 Correct 470 ms 23088 KB Ok
81 Correct 473 ms 22996 KB Ok
82 Correct 465 ms 22908 KB Ok
83 Correct 461 ms 22376 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 19092 KB Ok
2 Correct 43 ms 19104 KB Ok
3 Correct 47 ms 13208 KB Ok
4 Correct 40 ms 13288 KB Ok
5 Correct 37 ms 13260 KB Ok
6 Correct 50 ms 14412 KB Ok
7 Correct 41 ms 13272 KB Ok
8 Correct 39 ms 14416 KB Ok
9 Correct 42 ms 12996 KB Ok
10 Correct 39 ms 15904 KB Ok
11 Correct 41 ms 13160 KB Ok
12 Correct 59 ms 13028 KB Ok
13 Correct 53 ms 15936 KB Ok
14 Correct 40 ms 15948 KB Ok
15 Correct 43 ms 15980 KB Ok
16 Correct 39 ms 15948 KB Ok
17 Correct 40 ms 15948 KB Ok
18 Correct 45 ms 16088 KB Ok
19 Correct 71 ms 16640 KB Ok
20 Correct 56 ms 16276 KB Ok
21 Correct 62 ms 16772 KB Ok
22 Correct 50 ms 16444 KB Ok
23 Correct 23 ms 19020 KB Ok
24 Correct 47 ms 19100 KB Ok
25 Correct 43 ms 15932 KB Ok
26 Correct 39 ms 14940 KB Ok
27 Correct 48 ms 19100 KB Ok
28 Correct 44 ms 19012 KB Ok
29 Correct 40 ms 19108 KB Ok
30 Correct 40 ms 19020 KB Ok
31 Correct 40 ms 19128 KB Ok
32 Correct 39 ms 15956 KB Ok
33 Correct 42 ms 14924 KB Ok
34 Correct 45 ms 15964 KB Ok
35 Correct 45 ms 13644 KB Ok
36 Correct 38 ms 13260 KB Ok
37 Correct 37 ms 13132 KB Ok
38 Correct 40 ms 13076 KB Ok
39 Correct 266 ms 22428 KB Ok
40 Correct 247 ms 22768 KB Ok
41 Correct 464 ms 25768 KB Ok
42 Correct 327 ms 24184 KB Ok
43 Correct 211 ms 18308 KB Ok
44 Correct 268 ms 24204 KB Ok
45 Correct 51 ms 12932 KB Ok
46 Correct 46 ms 12940 KB Ok
47 Correct 50 ms 13008 KB Ok
48 Correct 49 ms 12876 KB Ok
49 Correct 45 ms 12960 KB Ok
50 Correct 43 ms 12936 KB Ok
51 Correct 47 ms 12912 KB Ok
52 Correct 57 ms 12912 KB Ok
53 Correct 43 ms 12944 KB Ok
54 Correct 44 ms 12880 KB Ok
55 Correct 55 ms 13084 KB Ok
56 Correct 57 ms 13144 KB Ok
57 Correct 66 ms 13052 KB Ok
58 Correct 73 ms 13088 KB Ok
59 Correct 57 ms 13052 KB Ok
60 Correct 54 ms 13084 KB Ok
61 Correct 76 ms 13056 KB Ok
62 Correct 58 ms 13080 KB Ok
63 Correct 57 ms 13076 KB Ok
64 Correct 60 ms 13128 KB Ok
65 Correct 177 ms 15404 KB Ok
66 Correct 242 ms 15712 KB Ok
67 Correct 238 ms 15728 KB Ok
68 Correct 147 ms 14916 KB Ok
69 Correct 190 ms 15188 KB Ok
70 Correct 192 ms 14976 KB Ok
71 Correct 167 ms 14836 KB Ok
72 Correct 154 ms 15092 KB Ok
73 Correct 205 ms 15476 KB Ok
74 Correct 161 ms 15136 KB Ok
75 Correct 218 ms 15676 KB Ok
76 Correct 169 ms 15296 KB Ok
77 Correct 162 ms 15136 KB Ok
78 Correct 150 ms 15084 KB Ok
79 Correct 164 ms 15368 KB Ok
80 Correct 463 ms 22920 KB Ok
81 Correct 484 ms 23444 KB Ok
82 Correct 451 ms 22884 KB Ok
83 Correct 450 ms 22748 KB Ok
84 Correct 467 ms 22924 KB Ok
85 Correct 487 ms 22712 KB Ok
86 Correct 472 ms 22276 KB Ok
87 Correct 522 ms 23244 KB Ok
88 Correct 449 ms 22320 KB Ok
89 Correct 482 ms 22796 KB Ok
90 Correct 460 ms 23060 KB Ok
91 Correct 470 ms 23088 KB Ok
92 Correct 473 ms 22996 KB Ok
93 Correct 465 ms 22908 KB Ok
94 Correct 461 ms 22376 KB Ok
95 Correct 403 ms 19672 KB Ok
96 Correct 553 ms 22736 KB Ok
97 Correct 482 ms 20784 KB Ok
98 Correct 348 ms 20492 KB Ok
99 Correct 433 ms 20208 KB Ok
100 Correct 492 ms 20360 KB Ok
101 Correct 524 ms 21372 KB Ok
102 Correct 453 ms 20544 KB Ok
103 Correct 494 ms 21432 KB Ok
104 Correct 556 ms 22492 KB Ok
105 Correct 553 ms 22536 KB Ok
106 Correct 458 ms 22396 KB Ok
107 Correct 505 ms 21932 KB Ok
108 Correct 599 ms 22608 KB Ok
109 Correct 569 ms 22944 KB Ok
110 Execution timed out 2079 ms 52740 KB Time limit exceeded
111 Halted 0 ms 0 KB -