oj.uz

Submission #496070

# Submission time Handle Problem Language Result Execution time Memory
496070 2021-12-20T13:55:52 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 33112 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 ];
vector <int> v[ 400001 ], ts, vv;

void dfs( int u ) {
	used[ u ] = 1;
	for ( auto to : v[ u ] ) {
		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 = 1; i <= x; i ++ ) {
		used[ i ] = 0;
		p[ i ] = 0;
		v[ i ].clear();
	}
	used[ 0 ] = 0;
	v[ 0 ].clear();
	for ( int i = n; i <= x; i ++ ) {
		v[ i - n ].push_back( i );
	}
	for ( int i = m; i <= x; i ++ ) {
		v[ i ].push_back( i - m );
	}
	ts.clear();
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	num = 0;
//	cout << x << " - ";
	for ( auto i : ts )
		p[ i ] = ++num;
//	for ( int i = 0; i <= x; i ++ )
//		cout << p[ i ] << " ";
//	cout << "\n";
	for ( int i = 1; i <= x; i ++ ) {
		p[ i ] -= p[ 0 ];
	}
	p[ 0 ] = 0;
	vv.clear();
	for ( int i = 1; i <= x; i ++ ) {
		vv.push_back( p[ i ] - p[ i - 1 ] );
	}
	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 = 200000;
		while ( r - l > 1 ) {
			mid = ( r + l ) / 2;
			if ( ok( mid ) )
				l = mid;
			else
				r = mid - 1;
		}
		if ( ok( r ) ) {
			cout << r << "\n";
			for ( auto i : vv )
				cout << i << " ";
		}
		else {
			ok( l );
			cout << l << "\n";
			for ( auto i : vv )
				cout << i << " ";
		}
		vv.clear();
		cout << "\n";
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18888 KB Ok
2 Correct 59 ms 18848 KB Ok
3 Correct 67 ms 14432 KB Ok
4 Correct 55 ms 14288 KB Ok
5 Correct 64 ms 14568 KB Ok
6 Correct 64 ms 15172 KB Ok
7 Correct 58 ms 14408 KB Ok
8 Correct 56 ms 15416 KB Ok
9 Correct 53 ms 14256 KB Ok
10 Correct 63 ms 16196 KB Ok
11 Correct 63 ms 14224 KB Ok
12 Correct 65 ms 13700 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 16584 KB Ok
2 Correct 60 ms 16444 KB Ok
3 Correct 60 ms 16544 KB Ok
4 Correct 56 ms 16476 KB Ok
5 Correct 58 ms 16584 KB Ok
6 Correct 65 ms 16764 KB Ok
7 Correct 94 ms 17320 KB Ok
8 Correct 76 ms 16836 KB Ok
9 Correct 101 ms 17400 KB Ok
10 Correct 85 ms 17084 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18624 KB Ok
2 Correct 65 ms 18728 KB Ok
3 Correct 54 ms 16368 KB Ok
4 Correct 62 ms 15812 KB Ok
5 Correct 58 ms 18956 KB Ok
6 Correct 57 ms 18696 KB Ok
7 Correct 58 ms 18880 KB Ok
8 Correct 57 ms 18832 KB Ok
9 Correct 59 ms 18752 KB Ok
10 Correct 63 ms 16392 KB Ok
11 Correct 55 ms 15652 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 16560 KB Ok
2 Correct 61 ms 14792 KB Ok
3 Correct 65 ms 14616 KB Ok
4 Correct 69 ms 14652 KB Ok
5 Correct 61 ms 14372 KB Ok
6 Correct 443 ms 28336 KB Ok
7 Correct 424 ms 30420 KB Ok
8 Correct 804 ms 33112 KB Ok
9 Correct 549 ms 30168 KB Ok
10 Correct 350 ms 21836 KB Ok
11 Correct 545 ms 31808 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18888 KB Ok
2 Correct 59 ms 18848 KB Ok
3 Correct 67 ms 14432 KB Ok
4 Correct 55 ms 14288 KB Ok
5 Correct 64 ms 14568 KB Ok
6 Correct 64 ms 15172 KB Ok
7 Correct 58 ms 14408 KB Ok
8 Correct 56 ms 15416 KB Ok
9 Correct 53 ms 14256 KB Ok
10 Correct 63 ms 16196 KB Ok
11 Correct 63 ms 14224 KB Ok
12 Correct 65 ms 13700 KB Ok
13 Correct 30 ms 18624 KB Ok
14 Correct 65 ms 18728 KB Ok
15 Correct 54 ms 16368 KB Ok
16 Correct 62 ms 15812 KB Ok
17 Correct 58 ms 18956 KB Ok
18 Correct 57 ms 18696 KB Ok
19 Correct 58 ms 18880 KB Ok
20 Correct 57 ms 18832 KB Ok
21 Correct 59 ms 18752 KB Ok
22 Correct 63 ms 16392 KB Ok
23 Correct 55 ms 15652 KB Ok
24 Correct 78 ms 14260 KB Ok
25 Correct 82 ms 14280 KB Ok
26 Correct 83 ms 14256 KB Ok
27 Correct 94 ms 14292 KB Ok
28 Correct 83 ms 14300 KB Ok
29 Correct 89 ms 14272 KB Ok
30 Correct 81 ms 14312 KB Ok
31 Correct 84 ms 14316 KB Ok
32 Correct 80 ms 14308 KB Ok
33 Correct 86 ms 14184 KB Ok
34 Correct 145 ms 14460 KB Ok
35 Correct 271 ms 14480 KB Ok
36 Correct 150 ms 14548 KB Ok
37 Correct 167 ms 14484 KB Ok
38 Correct 237 ms 14416 KB Ok
39 Correct 220 ms 14492 KB Ok
40 Correct 180 ms 14532 KB Ok
41 Correct 147 ms 14492 KB Ok
42 Correct 259 ms 14452 KB Ok
43 Correct 238 ms 14532 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18888 KB Ok
2 Correct 59 ms 18848 KB Ok
3 Correct 67 ms 14432 KB Ok
4 Correct 55 ms 14288 KB Ok
5 Correct 64 ms 14568 KB Ok
6 Correct 64 ms 15172 KB Ok
7 Correct 58 ms 14408 KB Ok
8 Correct 56 ms 15416 KB Ok
9 Correct 53 ms 14256 KB Ok
10 Correct 63 ms 16196 KB Ok
11 Correct 63 ms 14224 KB Ok
12 Correct 65 ms 13700 KB Ok
13 Correct 60 ms 16584 KB Ok
14 Correct 60 ms 16444 KB Ok
15 Correct 60 ms 16544 KB Ok
16 Correct 56 ms 16476 KB Ok
17 Correct 58 ms 16584 KB Ok
18 Correct 65 ms 16764 KB Ok
19 Correct 94 ms 17320 KB Ok
20 Correct 76 ms 16836 KB Ok
21 Correct 101 ms 17400 KB Ok
22 Correct 85 ms 17084 KB Ok
23 Correct 30 ms 18624 KB Ok
24 Correct 65 ms 18728 KB Ok
25 Correct 54 ms 16368 KB Ok
26 Correct 62 ms 15812 KB Ok
27 Correct 58 ms 18956 KB Ok
28 Correct 57 ms 18696 KB Ok
29 Correct 58 ms 18880 KB Ok
30 Correct 57 ms 18832 KB Ok
31 Correct 59 ms 18752 KB Ok
32 Correct 63 ms 16392 KB Ok
33 Correct 55 ms 15652 KB Ok
34 Correct 78 ms 14260 KB Ok
35 Correct 82 ms 14280 KB Ok
36 Correct 83 ms 14256 KB Ok
37 Correct 94 ms 14292 KB Ok
38 Correct 83 ms 14300 KB Ok
39 Correct 89 ms 14272 KB Ok
40 Correct 81 ms 14312 KB Ok
41 Correct 84 ms 14316 KB Ok
42 Correct 80 ms 14308 KB Ok
43 Correct 86 ms 14184 KB Ok
44 Correct 145 ms 14460 KB Ok
45 Correct 271 ms 14480 KB Ok
46 Correct 150 ms 14548 KB Ok
47 Correct 167 ms 14484 KB Ok
48 Correct 237 ms 14416 KB Ok
49 Correct 220 ms 14492 KB Ok
50 Correct 180 ms 14532 KB Ok
51 Correct 147 ms 14492 KB Ok
52 Correct 259 ms 14452 KB Ok
53 Correct 238 ms 14532 KB Ok
54 Correct 313 ms 17080 KB Ok
55 Correct 422 ms 17384 KB Ok
56 Correct 412 ms 17580 KB Ok
57 Correct 287 ms 16652 KB Ok
58 Correct 390 ms 16876 KB Ok
59 Correct 311 ms 16708 KB Ok
60 Correct 268 ms 16480 KB Ok
61 Correct 288 ms 16660 KB Ok
62 Correct 402 ms 17292 KB Ok
63 Correct 296 ms 16840 KB Ok
64 Correct 401 ms 17524 KB Ok
65 Correct 380 ms 17100 KB Ok
66 Correct 322 ms 16776 KB Ok
67 Correct 295 ms 16776 KB Ok
68 Correct 353 ms 16968 KB Ok
69 Correct 1442 ms 26228 KB Ok
70 Correct 1481 ms 27000 KB Ok
71 Correct 1491 ms 26272 KB Ok
72 Correct 1544 ms 26216 KB Ok
73 Correct 1690 ms 26352 KB Ok
74 Correct 1764 ms 26204 KB Ok
75 Correct 1464 ms 25772 KB Ok
76 Correct 1494 ms 26584 KB Ok
77 Correct 1383 ms 25736 KB Ok
78 Execution timed out 2090 ms 24488 KB Time limit exceeded
79 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18888 KB Ok
2 Correct 59 ms 18848 KB Ok
3 Correct 67 ms 14432 KB Ok
4 Correct 55 ms 14288 KB Ok
5 Correct 64 ms 14568 KB Ok
6 Correct 64 ms 15172 KB Ok
7 Correct 58 ms 14408 KB Ok
8 Correct 56 ms 15416 KB Ok
9 Correct 53 ms 14256 KB Ok
10 Correct 63 ms 16196 KB Ok
11 Correct 63 ms 14224 KB Ok
12 Correct 65 ms 13700 KB Ok
13 Correct 60 ms 16584 KB Ok
14 Correct 60 ms 16444 KB Ok
15 Correct 60 ms 16544 KB Ok
16 Correct 56 ms 16476 KB Ok
17 Correct 58 ms 16584 KB Ok
18 Correct 65 ms 16764 KB Ok
19 Correct 94 ms 17320 KB Ok
20 Correct 76 ms 16836 KB Ok
21 Correct 101 ms 17400 KB Ok
22 Correct 85 ms 17084 KB Ok
23 Correct 30 ms 18624 KB Ok
24 Correct 65 ms 18728 KB Ok
25 Correct 54 ms 16368 KB Ok
26 Correct 62 ms 15812 KB Ok
27 Correct 58 ms 18956 KB Ok
28 Correct 57 ms 18696 KB Ok
29 Correct 58 ms 18880 KB Ok
30 Correct 57 ms 18832 KB Ok
31 Correct 59 ms 18752 KB Ok
32 Correct 63 ms 16392 KB Ok
33 Correct 55 ms 15652 KB Ok
34 Correct 56 ms 16560 KB Ok
35 Correct 61 ms 14792 KB Ok
36 Correct 65 ms 14616 KB Ok
37 Correct 69 ms 14652 KB Ok
38 Correct 61 ms 14372 KB Ok
39 Correct 443 ms 28336 KB Ok
40 Correct 424 ms 30420 KB Ok
41 Correct 804 ms 33112 KB Ok
42 Correct 549 ms 30168 KB Ok
43 Correct 350 ms 21836 KB Ok
44 Correct 545 ms 31808 KB Ok
45 Correct 78 ms 14260 KB Ok
46 Correct 82 ms 14280 KB Ok
47 Correct 83 ms 14256 KB Ok
48 Correct 94 ms 14292 KB Ok
49 Correct 83 ms 14300 KB Ok
50 Correct 89 ms 14272 KB Ok
51 Correct 81 ms 14312 KB Ok
52 Correct 84 ms 14316 KB Ok
53 Correct 80 ms 14308 KB Ok
54 Correct 86 ms 14184 KB Ok
55 Correct 145 ms 14460 KB Ok
56 Correct 271 ms 14480 KB Ok
57 Correct 150 ms 14548 KB Ok
58 Correct 167 ms 14484 KB Ok
59 Correct 237 ms 14416 KB Ok
60 Correct 220 ms 14492 KB Ok
61 Correct 180 ms 14532 KB Ok
62 Correct 147 ms 14492 KB Ok
63 Correct 259 ms 14452 KB Ok
64 Correct 238 ms 14532 KB Ok
65 Correct 313 ms 17080 KB Ok
66 Correct 422 ms 17384 KB Ok
67 Correct 412 ms 17580 KB Ok
68 Correct 287 ms 16652 KB Ok
69 Correct 390 ms 16876 KB Ok
70 Correct 311 ms 16708 KB Ok
71 Correct 268 ms 16480 KB Ok
72 Correct 288 ms 16660 KB Ok
73 Correct 402 ms 17292 KB Ok
74 Correct 296 ms 16840 KB Ok
75 Correct 401 ms 17524 KB Ok
76 Correct 380 ms 17100 KB Ok
77 Correct 322 ms 16776 KB Ok
78 Correct 295 ms 16776 KB Ok
79 Correct 353 ms 16968 KB Ok
80 Correct 1442 ms 26228 KB Ok
81 Correct 1481 ms 27000 KB Ok
82 Correct 1491 ms 26272 KB Ok
83 Correct 1544 ms 26216 KB Ok
84 Correct 1690 ms 26352 KB Ok
85 Correct 1764 ms 26204 KB Ok
86 Correct 1464 ms 25772 KB Ok
87 Correct 1494 ms 26584 KB Ok
88 Correct 1383 ms 25736 KB Ok
89 Execution timed out 2090 ms 24488 KB Time limit exceeded
90 Halted 0 ms 0 KB -