oj.uz

Submission #496069

# Submission time Handle Problem Language Result Execution time Memory
496069 2021-12-20T13:54:36 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 35508 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 = 400000;
		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 130 ms 28056 KB Ok
2 Correct 134 ms 27836 KB Ok
3 Correct 167 ms 19072 KB Ok
4 Correct 154 ms 18824 KB Ok
5 Correct 165 ms 19260 KB Ok
6 Correct 182 ms 20712 KB Ok
7 Correct 154 ms 19036 KB Ok
8 Correct 164 ms 20924 KB Ok
9 Correct 141 ms 18808 KB Ok
10 Correct 142 ms 22640 KB Ok
11 Correct 151 ms 18632 KB Ok
12 Correct 152 ms 17760 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 23288 KB Ok
2 Correct 131 ms 23072 KB Ok
3 Correct 135 ms 23292 KB Ok
4 Correct 119 ms 23100 KB Ok
5 Correct 143 ms 23356 KB Ok
6 Correct 138 ms 23448 KB Ok
7 Correct 162 ms 23928 KB Ok
8 Correct 140 ms 23628 KB Ok
9 Correct 197 ms 24136 KB Ok
10 Correct 143 ms 23780 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 27576 KB Ok
2 Correct 153 ms 27688 KB Ok
3 Correct 144 ms 23016 KB Ok
4 Correct 124 ms 21768 KB Ok
5 Correct 148 ms 27964 KB Ok
6 Correct 140 ms 27680 KB Ok
7 Correct 150 ms 28016 KB Ok
8 Correct 137 ms 27700 KB Ok
9 Correct 126 ms 27624 KB Ok
10 Correct 143 ms 22952 KB Ok
11 Correct 130 ms 21452 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 23280 KB Ok
2 Correct 129 ms 19780 KB Ok
3 Correct 156 ms 19396 KB Ok
4 Correct 146 ms 19140 KB Ok
5 Correct 150 ms 19032 KB Ok
6 Correct 621 ms 31400 KB Ok
7 Correct 550 ms 33336 KB Ok
8 Correct 976 ms 35508 KB Ok
9 Correct 707 ms 33660 KB Ok
10 Correct 466 ms 26132 KB Ok
11 Correct 684 ms 34356 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 28056 KB Ok
2 Correct 134 ms 27836 KB Ok
3 Correct 167 ms 19072 KB Ok
4 Correct 154 ms 18824 KB Ok
5 Correct 165 ms 19260 KB Ok
6 Correct 182 ms 20712 KB Ok
7 Correct 154 ms 19036 KB Ok
8 Correct 164 ms 20924 KB Ok
9 Correct 141 ms 18808 KB Ok
10 Correct 142 ms 22640 KB Ok
11 Correct 151 ms 18632 KB Ok
12 Correct 152 ms 17760 KB Ok
13 Correct 56 ms 27576 KB Ok
14 Correct 153 ms 27688 KB Ok
15 Correct 144 ms 23016 KB Ok
16 Correct 124 ms 21768 KB Ok
17 Correct 148 ms 27964 KB Ok
18 Correct 140 ms 27680 KB Ok
19 Correct 150 ms 28016 KB Ok
20 Correct 137 ms 27700 KB Ok
21 Correct 126 ms 27624 KB Ok
22 Correct 143 ms 22952 KB Ok
23 Correct 130 ms 21452 KB Ok
24 Correct 192 ms 18668 KB Ok
25 Correct 224 ms 18676 KB Ok
26 Correct 195 ms 18632 KB Ok
27 Correct 198 ms 18740 KB Ok
28 Correct 250 ms 18700 KB Ok
29 Correct 211 ms 18688 KB Ok
30 Correct 212 ms 18628 KB Ok
31 Correct 238 ms 18664 KB Ok
32 Correct 202 ms 18628 KB Ok
33 Correct 265 ms 18700 KB Ok
34 Correct 567 ms 18796 KB Ok
35 Correct 588 ms 18836 KB Ok
36 Correct 576 ms 18840 KB Ok
37 Correct 516 ms 18884 KB Ok
38 Correct 571 ms 18836 KB Ok
39 Correct 569 ms 18876 KB Ok
40 Correct 564 ms 18828 KB Ok
41 Correct 660 ms 18924 KB Ok
42 Correct 730 ms 18872 KB Ok
43 Correct 556 ms 18824 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 28056 KB Ok
2 Correct 134 ms 27836 KB Ok
3 Correct 167 ms 19072 KB Ok
4 Correct 154 ms 18824 KB Ok
5 Correct 165 ms 19260 KB Ok
6 Correct 182 ms 20712 KB Ok
7 Correct 154 ms 19036 KB Ok
8 Correct 164 ms 20924 KB Ok
9 Correct 141 ms 18808 KB Ok
10 Correct 142 ms 22640 KB Ok
11 Correct 151 ms 18632 KB Ok
12 Correct 152 ms 17760 KB Ok
13 Correct 131 ms 23288 KB Ok
14 Correct 131 ms 23072 KB Ok
15 Correct 135 ms 23292 KB Ok
16 Correct 119 ms 23100 KB Ok
17 Correct 143 ms 23356 KB Ok
18 Correct 138 ms 23448 KB Ok
19 Correct 162 ms 23928 KB Ok
20 Correct 140 ms 23628 KB Ok
21 Correct 197 ms 24136 KB Ok
22 Correct 143 ms 23780 KB Ok
23 Correct 56 ms 27576 KB Ok
24 Correct 153 ms 27688 KB Ok
25 Correct 144 ms 23016 KB Ok
26 Correct 124 ms 21768 KB Ok
27 Correct 148 ms 27964 KB Ok
28 Correct 140 ms 27680 KB Ok
29 Correct 150 ms 28016 KB Ok
30 Correct 137 ms 27700 KB Ok
31 Correct 126 ms 27624 KB Ok
32 Correct 143 ms 22952 KB Ok
33 Correct 130 ms 21452 KB Ok
34 Correct 192 ms 18668 KB Ok
35 Correct 224 ms 18676 KB Ok
36 Correct 195 ms 18632 KB Ok
37 Correct 198 ms 18740 KB Ok
38 Correct 250 ms 18700 KB Ok
39 Correct 211 ms 18688 KB Ok
40 Correct 212 ms 18628 KB Ok
41 Correct 238 ms 18664 KB Ok
42 Correct 202 ms 18628 KB Ok
43 Correct 265 ms 18700 KB Ok
44 Correct 567 ms 18796 KB Ok
45 Correct 588 ms 18836 KB Ok
46 Correct 576 ms 18840 KB Ok
47 Correct 516 ms 18884 KB Ok
48 Correct 571 ms 18836 KB Ok
49 Correct 569 ms 18876 KB Ok
50 Correct 564 ms 18828 KB Ok
51 Correct 660 ms 18924 KB Ok
52 Correct 730 ms 18872 KB Ok
53 Correct 556 ms 18824 KB Ok
54 Correct 460 ms 21748 KB Ok
55 Correct 517 ms 22000 KB Ok
56 Correct 489 ms 21712 KB Ok
57 Correct 337 ms 20844 KB Ok
58 Correct 412 ms 21236 KB Ok
59 Correct 409 ms 21392 KB Ok
60 Correct 337 ms 21256 KB Ok
61 Correct 370 ms 21108 KB Ok
62 Correct 494 ms 22040 KB Ok
63 Correct 395 ms 21148 KB Ok
64 Correct 514 ms 21668 KB Ok
65 Correct 430 ms 21728 KB Ok
66 Correct 403 ms 21076 KB Ok
67 Correct 366 ms 21044 KB Ok
68 Correct 412 ms 21704 KB Ok
69 Execution timed out 2087 ms 29828 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 28056 KB Ok
2 Correct 134 ms 27836 KB Ok
3 Correct 167 ms 19072 KB Ok
4 Correct 154 ms 18824 KB Ok
5 Correct 165 ms 19260 KB Ok
6 Correct 182 ms 20712 KB Ok
7 Correct 154 ms 19036 KB Ok
8 Correct 164 ms 20924 KB Ok
9 Correct 141 ms 18808 KB Ok
10 Correct 142 ms 22640 KB Ok
11 Correct 151 ms 18632 KB Ok
12 Correct 152 ms 17760 KB Ok
13 Correct 131 ms 23288 KB Ok
14 Correct 131 ms 23072 KB Ok
15 Correct 135 ms 23292 KB Ok
16 Correct 119 ms 23100 KB Ok
17 Correct 143 ms 23356 KB Ok
18 Correct 138 ms 23448 KB Ok
19 Correct 162 ms 23928 KB Ok
20 Correct 140 ms 23628 KB Ok
21 Correct 197 ms 24136 KB Ok
22 Correct 143 ms 23780 KB Ok
23 Correct 56 ms 27576 KB Ok
24 Correct 153 ms 27688 KB Ok
25 Correct 144 ms 23016 KB Ok
26 Correct 124 ms 21768 KB Ok
27 Correct 148 ms 27964 KB Ok
28 Correct 140 ms 27680 KB Ok
29 Correct 150 ms 28016 KB Ok
30 Correct 137 ms 27700 KB Ok
31 Correct 126 ms 27624 KB Ok
32 Correct 143 ms 22952 KB Ok
33 Correct 130 ms 21452 KB Ok
34 Correct 128 ms 23280 KB Ok
35 Correct 129 ms 19780 KB Ok
36 Correct 156 ms 19396 KB Ok
37 Correct 146 ms 19140 KB Ok
38 Correct 150 ms 19032 KB Ok
39 Correct 621 ms 31400 KB Ok
40 Correct 550 ms 33336 KB Ok
41 Correct 976 ms 35508 KB Ok
42 Correct 707 ms 33660 KB Ok
43 Correct 466 ms 26132 KB Ok
44 Correct 684 ms 34356 KB Ok
45 Correct 192 ms 18668 KB Ok
46 Correct 224 ms 18676 KB Ok
47 Correct 195 ms 18632 KB Ok
48 Correct 198 ms 18740 KB Ok
49 Correct 250 ms 18700 KB Ok
50 Correct 211 ms 18688 KB Ok
51 Correct 212 ms 18628 KB Ok
52 Correct 238 ms 18664 KB Ok
53 Correct 202 ms 18628 KB Ok
54 Correct 265 ms 18700 KB Ok
55 Correct 567 ms 18796 KB Ok
56 Correct 588 ms 18836 KB Ok
57 Correct 576 ms 18840 KB Ok
58 Correct 516 ms 18884 KB Ok
59 Correct 571 ms 18836 KB Ok
60 Correct 569 ms 18876 KB Ok
61 Correct 564 ms 18828 KB Ok
62 Correct 660 ms 18924 KB Ok
63 Correct 730 ms 18872 KB Ok
64 Correct 556 ms 18824 KB Ok
65 Correct 460 ms 21748 KB Ok
66 Correct 517 ms 22000 KB Ok
67 Correct 489 ms 21712 KB Ok
68 Correct 337 ms 20844 KB Ok
69 Correct 412 ms 21236 KB Ok
70 Correct 409 ms 21392 KB Ok
71 Correct 337 ms 21256 KB Ok
72 Correct 370 ms 21108 KB Ok
73 Correct 494 ms 22040 KB Ok
74 Correct 395 ms 21148 KB Ok
75 Correct 514 ms 21668 KB Ok
76 Correct 430 ms 21728 KB Ok
77 Correct 403 ms 21076 KB Ok
78 Correct 366 ms 21044 KB Ok
79 Correct 412 ms 21704 KB Ok
80 Execution timed out 2087 ms 29828 KB Time limit exceeded
81 Halted 0 ms 0 KB -