oj.uz

Submission #496130

# Submission time Handle Problem Language Result Execution time Memory
496130 2021-12-20T18:24:05 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
76 / 100
 497 ms 24928 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 = 300000;
		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 30 ms 16756 KB Ok
2 Correct 32 ms 16760 KB Ok
3 Correct 31 ms 12364 KB Ok
4 Correct 32 ms 12360 KB Ok
5 Correct 31 ms 12384 KB Ok
6 Correct 40 ms 13220 KB Ok
7 Correct 31 ms 12312 KB Ok
8 Correct 37 ms 13240 KB Ok
9 Correct 27 ms 12140 KB Ok
10 Correct 29 ms 14364 KB Ok
11 Correct 33 ms 12236 KB Ok
12 Correct 30 ms 12224 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14412 KB Ok
2 Correct 38 ms 14412 KB Ok
3 Correct 37 ms 14424 KB Ok
4 Correct 30 ms 14420 KB Ok
5 Correct 36 ms 14372 KB Ok
6 Correct 33 ms 14524 KB Ok
7 Correct 48 ms 15132 KB Ok
8 Correct 48 ms 14708 KB Ok
9 Correct 72 ms 15252 KB Ok
10 Correct 47 ms 14888 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16716 KB Ok
2 Correct 36 ms 16716 KB Ok
3 Correct 30 ms 14412 KB Ok
4 Correct 29 ms 13616 KB Ok
5 Correct 29 ms 16716 KB Ok
6 Correct 30 ms 16708 KB Ok
7 Correct 38 ms 16716 KB Ok
8 Correct 41 ms 16716 KB Ok
9 Correct 33 ms 16752 KB Ok
10 Correct 30 ms 14412 KB Ok
11 Correct 31 ms 13724 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14420 KB Ok
2 Correct 30 ms 12620 KB Ok
3 Correct 30 ms 12428 KB Ok
4 Correct 32 ms 12236 KB Ok
5 Correct 35 ms 12284 KB Ok
6 Correct 261 ms 21672 KB Ok
7 Correct 254 ms 22088 KB Ok
8 Correct 444 ms 24928 KB Ok
9 Correct 323 ms 23428 KB Ok
10 Correct 191 ms 17464 KB Ok
11 Correct 284 ms 23384 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16756 KB Ok
2 Correct 32 ms 16760 KB Ok
3 Correct 31 ms 12364 KB Ok
4 Correct 32 ms 12360 KB Ok
5 Correct 31 ms 12384 KB Ok
6 Correct 40 ms 13220 KB Ok
7 Correct 31 ms 12312 KB Ok
8 Correct 37 ms 13240 KB Ok
9 Correct 27 ms 12140 KB Ok
10 Correct 29 ms 14364 KB Ok
11 Correct 33 ms 12236 KB Ok
12 Correct 30 ms 12224 KB Ok
13 Correct 14 ms 16716 KB Ok
14 Correct 36 ms 16716 KB Ok
15 Correct 30 ms 14412 KB Ok
16 Correct 29 ms 13616 KB Ok
17 Correct 29 ms 16716 KB Ok
18 Correct 30 ms 16708 KB Ok
19 Correct 38 ms 16716 KB Ok
20 Correct 41 ms 16716 KB Ok
21 Correct 33 ms 16752 KB Ok
22 Correct 30 ms 14412 KB Ok
23 Correct 31 ms 13724 KB Ok
24 Correct 42 ms 12084 KB Ok
25 Correct 45 ms 12092 KB Ok
26 Correct 37 ms 12108 KB Ok
27 Correct 39 ms 12156 KB Ok
28 Correct 39 ms 12104 KB Ok
29 Correct 35 ms 12128 KB Ok
30 Correct 45 ms 12128 KB Ok
31 Correct 70 ms 12120 KB Ok
32 Correct 40 ms 12144 KB Ok
33 Correct 35 ms 12108 KB Ok
34 Correct 50 ms 12252 KB Ok
35 Correct 44 ms 12336 KB Ok
36 Correct 48 ms 12356 KB Ok
37 Correct 57 ms 12320 KB Ok
38 Correct 58 ms 12272 KB Ok
39 Correct 45 ms 12284 KB Ok
40 Correct 46 ms 12280 KB Ok
41 Correct 47 ms 12420 KB Ok
42 Correct 61 ms 12276 KB Ok
43 Correct 65 ms 12356 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16756 KB Ok
2 Correct 32 ms 16760 KB Ok
3 Correct 31 ms 12364 KB Ok
4 Correct 32 ms 12360 KB Ok
5 Correct 31 ms 12384 KB Ok
6 Correct 40 ms 13220 KB Ok
7 Correct 31 ms 12312 KB Ok
8 Correct 37 ms 13240 KB Ok
9 Correct 27 ms 12140 KB Ok
10 Correct 29 ms 14364 KB Ok
11 Correct 33 ms 12236 KB Ok
12 Correct 30 ms 12224 KB Ok
13 Correct 33 ms 14412 KB Ok
14 Correct 38 ms 14412 KB Ok
15 Correct 37 ms 14424 KB Ok
16 Correct 30 ms 14420 KB Ok
17 Correct 36 ms 14372 KB Ok
18 Correct 33 ms 14524 KB Ok
19 Correct 48 ms 15132 KB Ok
20 Correct 48 ms 14708 KB Ok
21 Correct 72 ms 15252 KB Ok
22 Correct 47 ms 14888 KB Ok
23 Correct 14 ms 16716 KB Ok
24 Correct 36 ms 16716 KB Ok
25 Correct 30 ms 14412 KB Ok
26 Correct 29 ms 13616 KB Ok
27 Correct 29 ms 16716 KB Ok
28 Correct 30 ms 16708 KB Ok
29 Correct 38 ms 16716 KB Ok
30 Correct 41 ms 16716 KB Ok
31 Correct 33 ms 16752 KB Ok
32 Correct 30 ms 14412 KB Ok
33 Correct 31 ms 13724 KB Ok
34 Correct 42 ms 12084 KB Ok
35 Correct 45 ms 12092 KB Ok
36 Correct 37 ms 12108 KB Ok
37 Correct 39 ms 12156 KB Ok
38 Correct 39 ms 12104 KB Ok
39 Correct 35 ms 12128 KB Ok
40 Correct 45 ms 12128 KB Ok
41 Correct 70 ms 12120 KB Ok
42 Correct 40 ms 12144 KB Ok
43 Correct 35 ms 12108 KB Ok
44 Correct 50 ms 12252 KB Ok
45 Correct 44 ms 12336 KB Ok
46 Correct 48 ms 12356 KB Ok
47 Correct 57 ms 12320 KB Ok
48 Correct 58 ms 12272 KB Ok
49 Correct 45 ms 12284 KB Ok
50 Correct 46 ms 12280 KB Ok
51 Correct 47 ms 12420 KB Ok
52 Correct 61 ms 12276 KB Ok
53 Correct 65 ms 12356 KB Ok
54 Correct 178 ms 14616 KB Ok
55 Correct 201 ms 14868 KB Ok
56 Correct 210 ms 14916 KB Ok
57 Correct 138 ms 14116 KB Ok
58 Correct 169 ms 14420 KB Ok
59 Correct 143 ms 14216 KB Ok
60 Correct 133 ms 13996 KB Ok
61 Correct 158 ms 14188 KB Ok
62 Correct 174 ms 14632 KB Ok
63 Correct 157 ms 14336 KB Ok
64 Correct 221 ms 14848 KB Ok
65 Correct 165 ms 14556 KB Ok
66 Correct 155 ms 14308 KB Ok
67 Correct 140 ms 14300 KB Ok
68 Correct 159 ms 14468 KB Ok
69 Correct 422 ms 22124 KB Ok
70 Correct 431 ms 22564 KB Ok
71 Correct 456 ms 22276 KB Ok
72 Correct 393 ms 22004 KB Ok
73 Correct 404 ms 22100 KB Ok
74 Correct 425 ms 21944 KB Ok
75 Correct 457 ms 21492 KB Ok
76 Correct 427 ms 22276 KB Ok
77 Correct 423 ms 21548 KB Ok
78 Correct 422 ms 22132 KB Ok
79 Correct 422 ms 22284 KB Ok
80 Correct 420 ms 22368 KB Ok
81 Correct 397 ms 22256 KB Ok
82 Correct 404 ms 22264 KB Ok
83 Correct 430 ms 21684 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16756 KB Ok
2 Correct 32 ms 16760 KB Ok
3 Correct 31 ms 12364 KB Ok
4 Correct 32 ms 12360 KB Ok
5 Correct 31 ms 12384 KB Ok
6 Correct 40 ms 13220 KB Ok
7 Correct 31 ms 12312 KB Ok
8 Correct 37 ms 13240 KB Ok
9 Correct 27 ms 12140 KB Ok
10 Correct 29 ms 14364 KB Ok
11 Correct 33 ms 12236 KB Ok
12 Correct 30 ms 12224 KB Ok
13 Correct 33 ms 14412 KB Ok
14 Correct 38 ms 14412 KB Ok
15 Correct 37 ms 14424 KB Ok
16 Correct 30 ms 14420 KB Ok
17 Correct 36 ms 14372 KB Ok
18 Correct 33 ms 14524 KB Ok
19 Correct 48 ms 15132 KB Ok
20 Correct 48 ms 14708 KB Ok
21 Correct 72 ms 15252 KB Ok
22 Correct 47 ms 14888 KB Ok
23 Correct 14 ms 16716 KB Ok
24 Correct 36 ms 16716 KB Ok
25 Correct 30 ms 14412 KB Ok
26 Correct 29 ms 13616 KB Ok
27 Correct 29 ms 16716 KB Ok
28 Correct 30 ms 16708 KB Ok
29 Correct 38 ms 16716 KB Ok
30 Correct 41 ms 16716 KB Ok
31 Correct 33 ms 16752 KB Ok
32 Correct 30 ms 14412 KB Ok
33 Correct 31 ms 13724 KB Ok
34 Correct 29 ms 14420 KB Ok
35 Correct 30 ms 12620 KB Ok
36 Correct 30 ms 12428 KB Ok
37 Correct 32 ms 12236 KB Ok
38 Correct 35 ms 12284 KB Ok
39 Correct 261 ms 21672 KB Ok
40 Correct 254 ms 22088 KB Ok
41 Correct 444 ms 24928 KB Ok
42 Correct 323 ms 23428 KB Ok
43 Correct 191 ms 17464 KB Ok
44 Correct 284 ms 23384 KB Ok
45 Correct 42 ms 12084 KB Ok
46 Correct 45 ms 12092 KB Ok
47 Correct 37 ms 12108 KB Ok
48 Correct 39 ms 12156 KB Ok
49 Correct 39 ms 12104 KB Ok
50 Correct 35 ms 12128 KB Ok
51 Correct 45 ms 12128 KB Ok
52 Correct 70 ms 12120 KB Ok
53 Correct 40 ms 12144 KB Ok
54 Correct 35 ms 12108 KB Ok
55 Correct 50 ms 12252 KB Ok
56 Correct 44 ms 12336 KB Ok
57 Correct 48 ms 12356 KB Ok
58 Correct 57 ms 12320 KB Ok
59 Correct 58 ms 12272 KB Ok
60 Correct 45 ms 12284 KB Ok
61 Correct 46 ms 12280 KB Ok
62 Correct 47 ms 12420 KB Ok
63 Correct 61 ms 12276 KB Ok
64 Correct 65 ms 12356 KB Ok
65 Correct 178 ms 14616 KB Ok
66 Correct 201 ms 14868 KB Ok
67 Correct 210 ms 14916 KB Ok
68 Correct 138 ms 14116 KB Ok
69 Correct 169 ms 14420 KB Ok
70 Correct 143 ms 14216 KB Ok
71 Correct 133 ms 13996 KB Ok
72 Correct 158 ms 14188 KB Ok
73 Correct 174 ms 14632 KB Ok
74 Correct 157 ms 14336 KB Ok
75 Correct 221 ms 14848 KB Ok
76 Correct 165 ms 14556 KB Ok
77 Correct 155 ms 14308 KB Ok
78 Correct 140 ms 14300 KB Ok
79 Correct 159 ms 14468 KB Ok
80 Correct 422 ms 22124 KB Ok
81 Correct 431 ms 22564 KB Ok
82 Correct 456 ms 22276 KB Ok
83 Correct 393 ms 22004 KB Ok
84 Correct 404 ms 22100 KB Ok
85 Correct 425 ms 21944 KB Ok
86 Correct 457 ms 21492 KB Ok
87 Correct 427 ms 22276 KB Ok
88 Correct 423 ms 21548 KB Ok
89 Correct 422 ms 22132 KB Ok
90 Correct 422 ms 22284 KB Ok
91 Correct 420 ms 22368 KB Ok
92 Correct 397 ms 22256 KB Ok
93 Correct 404 ms 22264 KB Ok
94 Correct 430 ms 21684 KB Ok
95 Correct 420 ms 19184 KB Ok
96 Incorrect 497 ms 21064 KB Jury has the better answer : jans = 311847, pans = 300000
97 Halted 0 ms 0 KB -