oj.uz

Submission #496121

# Submission time Handle Problem Language Result Execution time Memory
496121 2021-12-20T18:06:42 Z vinnipuh01 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 54360 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;
		}
	}
	ts.push_back( u );
	used[ u ] = 2;
}
 
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;
	}
	ts.clear();
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	num = 0;
	for ( auto i : ts )
		p[ i ] = ++num;
	for ( int i = 1; i <= x; i ++ ) {
		p[ i ] -= p[ 0 ];
	}
	p[ 0 ] = 0;
	if ( sum ) {
		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;
		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 ( auto i : vv )
				cout << i << " ";
		}
		else {
			sum = 1;
			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 47 ms 20172 KB Ok
2 Correct 50 ms 19980 KB Ok
3 Correct 47 ms 14196 KB Ok
4 Correct 46 ms 13848 KB Ok
5 Correct 49 ms 14448 KB Ok
6 Correct 48 ms 15176 KB Ok
7 Correct 44 ms 14284 KB Ok
8 Correct 53 ms 15560 KB Ok
9 Correct 45 ms 14072 KB Ok
10 Correct 50 ms 16452 KB Ok
11 Correct 61 ms 13768 KB Ok
12 Correct 44 ms 13032 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17100 KB Ok
2 Correct 49 ms 16800 KB Ok
3 Correct 50 ms 17072 KB Ok
4 Correct 53 ms 16860 KB Ok
5 Correct 49 ms 17100 KB Ok
6 Correct 55 ms 17220 KB Ok
7 Correct 79 ms 17612 KB Ok
8 Correct 60 ms 17320 KB Ok
9 Correct 75 ms 17596 KB Ok
10 Correct 66 ms 17400 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19748 KB Ok
2 Correct 51 ms 19948 KB Ok
3 Correct 49 ms 16772 KB Ok
4 Correct 59 ms 16144 KB Ok
5 Correct 54 ms 20292 KB Ok
6 Correct 47 ms 19904 KB Ok
7 Correct 46 ms 20228 KB Ok
8 Correct 52 ms 19920 KB Ok
9 Correct 47 ms 19868 KB Ok
10 Correct 48 ms 16800 KB Ok
11 Correct 46 ms 15680 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17100 KB Ok
2 Correct 48 ms 14796 KB Ok
3 Correct 48 ms 14412 KB Ok
4 Correct 50 ms 14284 KB Ok
5 Correct 54 ms 14276 KB Ok
6 Correct 338 ms 23348 KB Ok
7 Correct 314 ms 23760 KB Ok
8 Correct 573 ms 26836 KB Ok
9 Correct 428 ms 25088 KB Ok
10 Correct 253 ms 19644 KB Ok
11 Correct 392 ms 25148 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20172 KB Ok
2 Correct 50 ms 19980 KB Ok
3 Correct 47 ms 14196 KB Ok
4 Correct 46 ms 13848 KB Ok
5 Correct 49 ms 14448 KB Ok
6 Correct 48 ms 15176 KB Ok
7 Correct 44 ms 14284 KB Ok
8 Correct 53 ms 15560 KB Ok
9 Correct 45 ms 14072 KB Ok
10 Correct 50 ms 16452 KB Ok
11 Correct 61 ms 13768 KB Ok
12 Correct 44 ms 13032 KB Ok
13 Correct 23 ms 19748 KB Ok
14 Correct 51 ms 19948 KB Ok
15 Correct 49 ms 16772 KB Ok
16 Correct 59 ms 16144 KB Ok
17 Correct 54 ms 20292 KB Ok
18 Correct 47 ms 19904 KB Ok
19 Correct 46 ms 20228 KB Ok
20 Correct 52 ms 19920 KB Ok
21 Correct 47 ms 19868 KB Ok
22 Correct 48 ms 16800 KB Ok
23 Correct 46 ms 15680 KB Ok
24 Correct 56 ms 14028 KB Ok
25 Correct 58 ms 14032 KB Ok
26 Correct 54 ms 14028 KB Ok
27 Correct 54 ms 14068 KB Ok
28 Correct 58 ms 14028 KB Ok
29 Correct 48 ms 13960 KB Ok
30 Correct 54 ms 13932 KB Ok
31 Correct 56 ms 14068 KB Ok
32 Correct 53 ms 14028 KB Ok
33 Correct 55 ms 14028 KB Ok
34 Correct 75 ms 14028 KB Ok
35 Correct 73 ms 14028 KB Ok
36 Correct 80 ms 14028 KB Ok
37 Correct 93 ms 14048 KB Ok
38 Correct 71 ms 14028 KB Ok
39 Correct 73 ms 14028 KB Ok
40 Correct 73 ms 14156 KB Ok
41 Correct 71 ms 14156 KB Ok
42 Correct 73 ms 14156 KB Ok
43 Correct 86 ms 14156 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20172 KB Ok
2 Correct 50 ms 19980 KB Ok
3 Correct 47 ms 14196 KB Ok
4 Correct 46 ms 13848 KB Ok
5 Correct 49 ms 14448 KB Ok
6 Correct 48 ms 15176 KB Ok
7 Correct 44 ms 14284 KB Ok
8 Correct 53 ms 15560 KB Ok
9 Correct 45 ms 14072 KB Ok
10 Correct 50 ms 16452 KB Ok
11 Correct 61 ms 13768 KB Ok
12 Correct 44 ms 13032 KB Ok
13 Correct 47 ms 17100 KB Ok
14 Correct 49 ms 16800 KB Ok
15 Correct 50 ms 17072 KB Ok
16 Correct 53 ms 16860 KB Ok
17 Correct 49 ms 17100 KB Ok
18 Correct 55 ms 17220 KB Ok
19 Correct 79 ms 17612 KB Ok
20 Correct 60 ms 17320 KB Ok
21 Correct 75 ms 17596 KB Ok
22 Correct 66 ms 17400 KB Ok
23 Correct 23 ms 19748 KB Ok
24 Correct 51 ms 19948 KB Ok
25 Correct 49 ms 16772 KB Ok
26 Correct 59 ms 16144 KB Ok
27 Correct 54 ms 20292 KB Ok
28 Correct 47 ms 19904 KB Ok
29 Correct 46 ms 20228 KB Ok
30 Correct 52 ms 19920 KB Ok
31 Correct 47 ms 19868 KB Ok
32 Correct 48 ms 16800 KB Ok
33 Correct 46 ms 15680 KB Ok
34 Correct 56 ms 14028 KB Ok
35 Correct 58 ms 14032 KB Ok
36 Correct 54 ms 14028 KB Ok
37 Correct 54 ms 14068 KB Ok
38 Correct 58 ms 14028 KB Ok
39 Correct 48 ms 13960 KB Ok
40 Correct 54 ms 13932 KB Ok
41 Correct 56 ms 14068 KB Ok
42 Correct 53 ms 14028 KB Ok
43 Correct 55 ms 14028 KB Ok
44 Correct 75 ms 14028 KB Ok
45 Correct 73 ms 14028 KB Ok
46 Correct 80 ms 14028 KB Ok
47 Correct 93 ms 14048 KB Ok
48 Correct 71 ms 14028 KB Ok
49 Correct 73 ms 14028 KB Ok
50 Correct 73 ms 14156 KB Ok
51 Correct 71 ms 14156 KB Ok
52 Correct 73 ms 14156 KB Ok
53 Correct 86 ms 14156 KB Ok
54 Correct 253 ms 16572 KB Ok
55 Correct 298 ms 16948 KB Ok
56 Correct 293 ms 16380 KB Ok
57 Correct 202 ms 15708 KB Ok
58 Correct 254 ms 15892 KB Ok
59 Correct 227 ms 16232 KB Ok
60 Correct 209 ms 16004 KB Ok
61 Correct 213 ms 15668 KB Ok
62 Correct 277 ms 16628 KB Ok
63 Correct 248 ms 15820 KB Ok
64 Correct 292 ms 16500 KB Ok
65 Correct 257 ms 16448 KB Ok
66 Correct 234 ms 15896 KB Ok
67 Correct 205 ms 15796 KB Ok
68 Correct 244 ms 16600 KB Ok
69 Correct 569 ms 24272 KB Ok
70 Correct 546 ms 24844 KB Ok
71 Correct 531 ms 24168 KB Ok
72 Correct 511 ms 24176 KB Ok
73 Correct 554 ms 24160 KB Ok
74 Correct 571 ms 24180 KB Ok
75 Correct 564 ms 23528 KB Ok
76 Correct 563 ms 24452 KB Ok
77 Correct 540 ms 23688 KB Ok
78 Correct 548 ms 24172 KB Ok
79 Correct 542 ms 24284 KB Ok
80 Correct 528 ms 24372 KB Ok
81 Correct 536 ms 24204 KB Ok
82 Correct 530 ms 24248 KB Ok
83 Correct 530 ms 23800 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 20172 KB Ok
2 Correct 50 ms 19980 KB Ok
3 Correct 47 ms 14196 KB Ok
4 Correct 46 ms 13848 KB Ok
5 Correct 49 ms 14448 KB Ok
6 Correct 48 ms 15176 KB Ok
7 Correct 44 ms 14284 KB Ok
8 Correct 53 ms 15560 KB Ok
9 Correct 45 ms 14072 KB Ok
10 Correct 50 ms 16452 KB Ok
11 Correct 61 ms 13768 KB Ok
12 Correct 44 ms 13032 KB Ok
13 Correct 47 ms 17100 KB Ok
14 Correct 49 ms 16800 KB Ok
15 Correct 50 ms 17072 KB Ok
16 Correct 53 ms 16860 KB Ok
17 Correct 49 ms 17100 KB Ok
18 Correct 55 ms 17220 KB Ok
19 Correct 79 ms 17612 KB Ok
20 Correct 60 ms 17320 KB Ok
21 Correct 75 ms 17596 KB Ok
22 Correct 66 ms 17400 KB Ok
23 Correct 23 ms 19748 KB Ok
24 Correct 51 ms 19948 KB Ok
25 Correct 49 ms 16772 KB Ok
26 Correct 59 ms 16144 KB Ok
27 Correct 54 ms 20292 KB Ok
28 Correct 47 ms 19904 KB Ok
29 Correct 46 ms 20228 KB Ok
30 Correct 52 ms 19920 KB Ok
31 Correct 47 ms 19868 KB Ok
32 Correct 48 ms 16800 KB Ok
33 Correct 46 ms 15680 KB Ok
34 Correct 47 ms 17100 KB Ok
35 Correct 48 ms 14796 KB Ok
36 Correct 48 ms 14412 KB Ok
37 Correct 50 ms 14284 KB Ok
38 Correct 54 ms 14276 KB Ok
39 Correct 338 ms 23348 KB Ok
40 Correct 314 ms 23760 KB Ok
41 Correct 573 ms 26836 KB Ok
42 Correct 428 ms 25088 KB Ok
43 Correct 253 ms 19644 KB Ok
44 Correct 392 ms 25148 KB Ok
45 Correct 56 ms 14028 KB Ok
46 Correct 58 ms 14032 KB Ok
47 Correct 54 ms 14028 KB Ok
48 Correct 54 ms 14068 KB Ok
49 Correct 58 ms 14028 KB Ok
50 Correct 48 ms 13960 KB Ok
51 Correct 54 ms 13932 KB Ok
52 Correct 56 ms 14068 KB Ok
53 Correct 53 ms 14028 KB Ok
54 Correct 55 ms 14028 KB Ok
55 Correct 75 ms 14028 KB Ok
56 Correct 73 ms 14028 KB Ok
57 Correct 80 ms 14028 KB Ok
58 Correct 93 ms 14048 KB Ok
59 Correct 71 ms 14028 KB Ok
60 Correct 73 ms 14028 KB Ok
61 Correct 73 ms 14156 KB Ok
62 Correct 71 ms 14156 KB Ok
63 Correct 73 ms 14156 KB Ok
64 Correct 86 ms 14156 KB Ok
65 Correct 253 ms 16572 KB Ok
66 Correct 298 ms 16948 KB Ok
67 Correct 293 ms 16380 KB Ok
68 Correct 202 ms 15708 KB Ok
69 Correct 254 ms 15892 KB Ok
70 Correct 227 ms 16232 KB Ok
71 Correct 209 ms 16004 KB Ok
72 Correct 213 ms 15668 KB Ok
73 Correct 277 ms 16628 KB Ok
74 Correct 248 ms 15820 KB Ok
75 Correct 292 ms 16500 KB Ok
76 Correct 257 ms 16448 KB Ok
77 Correct 234 ms 15896 KB Ok
78 Correct 205 ms 15796 KB Ok
79 Correct 244 ms 16600 KB Ok
80 Correct 569 ms 24272 KB Ok
81 Correct 546 ms 24844 KB Ok
82 Correct 531 ms 24168 KB Ok
83 Correct 511 ms 24176 KB Ok
84 Correct 554 ms 24160 KB Ok
85 Correct 571 ms 24180 KB Ok
86 Correct 564 ms 23528 KB Ok
87 Correct 563 ms 24452 KB Ok
88 Correct 540 ms 23688 KB Ok
89 Correct 548 ms 24172 KB Ok
90 Correct 542 ms 24284 KB Ok
91 Correct 528 ms 24372 KB Ok
92 Correct 536 ms 24204 KB Ok
93 Correct 530 ms 24248 KB Ok
94 Correct 530 ms 23800 KB Ok
95 Correct 537 ms 20800 KB Ok
96 Correct 774 ms 24108 KB Ok
97 Correct 726 ms 21848 KB Ok
98 Correct 524 ms 21720 KB Ok
99 Correct 640 ms 21252 KB Ok
100 Correct 743 ms 21492 KB Ok
101 Correct 708 ms 22744 KB Ok
102 Correct 641 ms 21664 KB Ok
103 Correct 673 ms 22656 KB Ok
104 Correct 807 ms 23904 KB Ok
105 Correct 771 ms 23992 KB Ok
106 Correct 666 ms 23736 KB Ok
107 Correct 738 ms 23100 KB Ok
108 Correct 802 ms 23948 KB Ok
109 Correct 750 ms 24540 KB Ok
110 Execution timed out 2074 ms 54360 KB Time limit exceeded
111 Halted 0 ms 0 KB -