oj.uz

Submission #496131

# Submission time Handle Problem Language Result Execution time Memory
496131 2021-12-20T18:25:04 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
76 / 100
 510 ms 25304 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 = 350000;
		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 44 ms 17876 KB Ok
2 Correct 39 ms 17924 KB Ok
3 Correct 51 ms 12788 KB Ok
4 Correct 34 ms 12748 KB Ok
5 Correct 37 ms 12748 KB Ok
6 Correct 34 ms 13772 KB Ok
7 Correct 35 ms 12728 KB Ok
8 Correct 50 ms 13772 KB Ok
9 Correct 38 ms 12604 KB Ok
10 Correct 47 ms 15160 KB Ok
11 Correct 41 ms 12620 KB Ok
12 Correct 47 ms 12616 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15180 KB Ok
2 Correct 34 ms 15096 KB Ok
3 Correct 38 ms 15196 KB Ok
4 Correct 34 ms 15180 KB Ok
5 Correct 37 ms 15172 KB Ok
6 Correct 51 ms 15296 KB Ok
7 Correct 71 ms 15868 KB Ok
8 Correct 49 ms 15528 KB Ok
9 Correct 54 ms 16032 KB Ok
10 Correct 47 ms 15688 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17876 KB Ok
2 Correct 36 ms 17868 KB Ok
3 Correct 35 ms 15180 KB Ok
4 Correct 36 ms 14284 KB Ok
5 Correct 36 ms 17928 KB Ok
6 Correct 48 ms 17932 KB Ok
7 Correct 48 ms 17928 KB Ok
8 Correct 45 ms 17920 KB Ok
9 Correct 34 ms 17880 KB Ok
10 Correct 32 ms 15184 KB Ok
11 Correct 32 ms 14284 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15180 KB Ok
2 Correct 35 ms 13208 KB Ok
3 Correct 31 ms 12876 KB Ok
4 Correct 36 ms 12732 KB Ok
5 Correct 36 ms 12620 KB Ok
6 Correct 253 ms 22064 KB Ok
7 Correct 306 ms 22332 KB Ok
8 Correct 442 ms 25304 KB Ok
9 Correct 320 ms 23720 KB Ok
10 Correct 197 ms 17860 KB Ok
11 Correct 268 ms 23844 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17876 KB Ok
2 Correct 39 ms 17924 KB Ok
3 Correct 51 ms 12788 KB Ok
4 Correct 34 ms 12748 KB Ok
5 Correct 37 ms 12748 KB Ok
6 Correct 34 ms 13772 KB Ok
7 Correct 35 ms 12728 KB Ok
8 Correct 50 ms 13772 KB Ok
9 Correct 38 ms 12604 KB Ok
10 Correct 47 ms 15160 KB Ok
11 Correct 41 ms 12620 KB Ok
12 Correct 47 ms 12616 KB Ok
13 Correct 17 ms 17876 KB Ok
14 Correct 36 ms 17868 KB Ok
15 Correct 35 ms 15180 KB Ok
16 Correct 36 ms 14284 KB Ok
17 Correct 36 ms 17928 KB Ok
18 Correct 48 ms 17932 KB Ok
19 Correct 48 ms 17928 KB Ok
20 Correct 45 ms 17920 KB Ok
21 Correct 34 ms 17880 KB Ok
22 Correct 32 ms 15184 KB Ok
23 Correct 32 ms 14284 KB Ok
24 Correct 44 ms 12532 KB Ok
25 Correct 39 ms 12492 KB Ok
26 Correct 44 ms 12492 KB Ok
27 Correct 44 ms 12532 KB Ok
28 Correct 44 ms 12508 KB Ok
29 Correct 50 ms 12500 KB Ok
30 Correct 51 ms 12632 KB Ok
31 Correct 44 ms 12460 KB Ok
32 Correct 43 ms 12612 KB Ok
33 Correct 42 ms 12532 KB Ok
34 Correct 57 ms 12624 KB Ok
35 Correct 68 ms 12672 KB Ok
36 Correct 59 ms 12740 KB Ok
37 Correct 56 ms 12740 KB Ok
38 Correct 50 ms 12700 KB Ok
39 Correct 64 ms 12696 KB Ok
40 Correct 68 ms 12752 KB Ok
41 Correct 69 ms 12740 KB Ok
42 Correct 54 ms 12696 KB Ok
43 Correct 74 ms 12740 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17876 KB Ok
2 Correct 39 ms 17924 KB Ok
3 Correct 51 ms 12788 KB Ok
4 Correct 34 ms 12748 KB Ok
5 Correct 37 ms 12748 KB Ok
6 Correct 34 ms 13772 KB Ok
7 Correct 35 ms 12728 KB Ok
8 Correct 50 ms 13772 KB Ok
9 Correct 38 ms 12604 KB Ok
10 Correct 47 ms 15160 KB Ok
11 Correct 41 ms 12620 KB Ok
12 Correct 47 ms 12616 KB Ok
13 Correct 32 ms 15180 KB Ok
14 Correct 34 ms 15096 KB Ok
15 Correct 38 ms 15196 KB Ok
16 Correct 34 ms 15180 KB Ok
17 Correct 37 ms 15172 KB Ok
18 Correct 51 ms 15296 KB Ok
19 Correct 71 ms 15868 KB Ok
20 Correct 49 ms 15528 KB Ok
21 Correct 54 ms 16032 KB Ok
22 Correct 47 ms 15688 KB Ok
23 Correct 17 ms 17876 KB Ok
24 Correct 36 ms 17868 KB Ok
25 Correct 35 ms 15180 KB Ok
26 Correct 36 ms 14284 KB Ok
27 Correct 36 ms 17928 KB Ok
28 Correct 48 ms 17932 KB Ok
29 Correct 48 ms 17928 KB Ok
30 Correct 45 ms 17920 KB Ok
31 Correct 34 ms 17880 KB Ok
32 Correct 32 ms 15184 KB Ok
33 Correct 32 ms 14284 KB Ok
34 Correct 44 ms 12532 KB Ok
35 Correct 39 ms 12492 KB Ok
36 Correct 44 ms 12492 KB Ok
37 Correct 44 ms 12532 KB Ok
38 Correct 44 ms 12508 KB Ok
39 Correct 50 ms 12500 KB Ok
40 Correct 51 ms 12632 KB Ok
41 Correct 44 ms 12460 KB Ok
42 Correct 43 ms 12612 KB Ok
43 Correct 42 ms 12532 KB Ok
44 Correct 57 ms 12624 KB Ok
45 Correct 68 ms 12672 KB Ok
46 Correct 59 ms 12740 KB Ok
47 Correct 56 ms 12740 KB Ok
48 Correct 50 ms 12700 KB Ok
49 Correct 64 ms 12696 KB Ok
50 Correct 68 ms 12752 KB Ok
51 Correct 69 ms 12740 KB Ok
52 Correct 54 ms 12696 KB Ok
53 Correct 74 ms 12740 KB Ok
54 Correct 183 ms 14932 KB Ok
55 Correct 242 ms 15296 KB Ok
56 Correct 215 ms 15556 KB Ok
57 Correct 136 ms 14604 KB Ok
58 Correct 172 ms 14840 KB Ok
59 Correct 177 ms 14700 KB Ok
60 Correct 129 ms 14416 KB Ok
61 Correct 152 ms 14532 KB Ok
62 Correct 186 ms 15040 KB Ok
63 Correct 179 ms 14716 KB Ok
64 Correct 200 ms 15296 KB Ok
65 Correct 205 ms 14912 KB Ok
66 Correct 150 ms 14792 KB Ok
67 Correct 190 ms 14704 KB Ok
68 Correct 162 ms 14900 KB Ok
69 Correct 480 ms 22392 KB Ok
70 Correct 439 ms 23128 KB Ok
71 Correct 445 ms 22452 KB Ok
72 Correct 425 ms 22460 KB Ok
73 Correct 418 ms 22420 KB Ok
74 Correct 447 ms 22320 KB Ok
75 Correct 477 ms 21896 KB Ok
76 Correct 424 ms 22868 KB Ok
77 Correct 442 ms 21940 KB Ok
78 Correct 443 ms 22440 KB Ok
79 Correct 403 ms 22620 KB Ok
80 Correct 396 ms 22720 KB Ok
81 Correct 422 ms 22596 KB Ok
82 Correct 406 ms 22512 KB Ok
83 Correct 392 ms 22068 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17876 KB Ok
2 Correct 39 ms 17924 KB Ok
3 Correct 51 ms 12788 KB Ok
4 Correct 34 ms 12748 KB Ok
5 Correct 37 ms 12748 KB Ok
6 Correct 34 ms 13772 KB Ok
7 Correct 35 ms 12728 KB Ok
8 Correct 50 ms 13772 KB Ok
9 Correct 38 ms 12604 KB Ok
10 Correct 47 ms 15160 KB Ok
11 Correct 41 ms 12620 KB Ok
12 Correct 47 ms 12616 KB Ok
13 Correct 32 ms 15180 KB Ok
14 Correct 34 ms 15096 KB Ok
15 Correct 38 ms 15196 KB Ok
16 Correct 34 ms 15180 KB Ok
17 Correct 37 ms 15172 KB Ok
18 Correct 51 ms 15296 KB Ok
19 Correct 71 ms 15868 KB Ok
20 Correct 49 ms 15528 KB Ok
21 Correct 54 ms 16032 KB Ok
22 Correct 47 ms 15688 KB Ok
23 Correct 17 ms 17876 KB Ok
24 Correct 36 ms 17868 KB Ok
25 Correct 35 ms 15180 KB Ok
26 Correct 36 ms 14284 KB Ok
27 Correct 36 ms 17928 KB Ok
28 Correct 48 ms 17932 KB Ok
29 Correct 48 ms 17928 KB Ok
30 Correct 45 ms 17920 KB Ok
31 Correct 34 ms 17880 KB Ok
32 Correct 32 ms 15184 KB Ok
33 Correct 32 ms 14284 KB Ok
34 Correct 34 ms 15180 KB Ok
35 Correct 35 ms 13208 KB Ok
36 Correct 31 ms 12876 KB Ok
37 Correct 36 ms 12732 KB Ok
38 Correct 36 ms 12620 KB Ok
39 Correct 253 ms 22064 KB Ok
40 Correct 306 ms 22332 KB Ok
41 Correct 442 ms 25304 KB Ok
42 Correct 320 ms 23720 KB Ok
43 Correct 197 ms 17860 KB Ok
44 Correct 268 ms 23844 KB Ok
45 Correct 44 ms 12532 KB Ok
46 Correct 39 ms 12492 KB Ok
47 Correct 44 ms 12492 KB Ok
48 Correct 44 ms 12532 KB Ok
49 Correct 44 ms 12508 KB Ok
50 Correct 50 ms 12500 KB Ok
51 Correct 51 ms 12632 KB Ok
52 Correct 44 ms 12460 KB Ok
53 Correct 43 ms 12612 KB Ok
54 Correct 42 ms 12532 KB Ok
55 Correct 57 ms 12624 KB Ok
56 Correct 68 ms 12672 KB Ok
57 Correct 59 ms 12740 KB Ok
58 Correct 56 ms 12740 KB Ok
59 Correct 50 ms 12700 KB Ok
60 Correct 64 ms 12696 KB Ok
61 Correct 68 ms 12752 KB Ok
62 Correct 69 ms 12740 KB Ok
63 Correct 54 ms 12696 KB Ok
64 Correct 74 ms 12740 KB Ok
65 Correct 183 ms 14932 KB Ok
66 Correct 242 ms 15296 KB Ok
67 Correct 215 ms 15556 KB Ok
68 Correct 136 ms 14604 KB Ok
69 Correct 172 ms 14840 KB Ok
70 Correct 177 ms 14700 KB Ok
71 Correct 129 ms 14416 KB Ok
72 Correct 152 ms 14532 KB Ok
73 Correct 186 ms 15040 KB Ok
74 Correct 179 ms 14716 KB Ok
75 Correct 200 ms 15296 KB Ok
76 Correct 205 ms 14912 KB Ok
77 Correct 150 ms 14792 KB Ok
78 Correct 190 ms 14704 KB Ok
79 Correct 162 ms 14900 KB Ok
80 Correct 480 ms 22392 KB Ok
81 Correct 439 ms 23128 KB Ok
82 Correct 445 ms 22452 KB Ok
83 Correct 425 ms 22460 KB Ok
84 Correct 418 ms 22420 KB Ok
85 Correct 447 ms 22320 KB Ok
86 Correct 477 ms 21896 KB Ok
87 Correct 424 ms 22868 KB Ok
88 Correct 442 ms 21940 KB Ok
89 Correct 443 ms 22440 KB Ok
90 Correct 403 ms 22620 KB Ok
91 Correct 396 ms 22720 KB Ok
92 Correct 422 ms 22596 KB Ok
93 Correct 406 ms 22512 KB Ok
94 Correct 392 ms 22068 KB Ok
95 Correct 379 ms 19364 KB Ok
96 Incorrect 510 ms 22236 KB Jury has the better answer : jans = 354419, pans = 350000
97 Halted 0 ms 0 KB -