답안 #496583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496583	2021-12-21T14:58:18 Z	vinnipuh01	Nice sequence (IZhO18_sequence)	C++11	100 / 100	1922 ms	47544 KB

sequence

#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 sz;
int n, m, p[ 400001 ], used[ 400001 ], nn[ 400001 ], mm[ 400001 ], ts[400001];
vector <int> vv;
 
inline void dfs( int u ) {
	used[ u ] = 1;
	for ( int i = 1; i <= 2; i ++ ) {
		int to;
		if ( ans )
			return;
		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;
		}
	}
		if ( ans )
			return;
	used[ u ] = 2;
}
 
inline 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[sz++] = u ;
}
 
bool ok( int x ) {
	for ( int i = 0; i <= x; i ++ ) {
		used[ i ] = 0;
		nn[ i ] = -1;
		mm[ i ] = -1; 
		if ( i >= n )
			nn[ i - n ] = i;
		if ( i >= m )
			mm[ i ] = i - m; 
	}
	ans = 0;
	for ( int i = 0; i <= x; i ++ ) {
		if ( !used[ i ] )
			dfs( i );
	}
	if ( ans )
		return false;
	if ( sum ) {
		sz = 0;
		for ( int i = 0; i <= x; i ++ ) {
			p[ i ] = 0;
			used[ i ] = 0;
		}
		for ( int i = 0; i<= x; i ++ ) {
			if ( !used[ i ] )
				dfs1( i );
		}
		num = 0;
        for (int j = 0; j < sz; j++) {
          int i = ts[j];
          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 = 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 ( 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

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	8000 KB	Ok
2	Correct	38 ms	7884 KB	Ok
3	Correct	46 ms	2996 KB	Ok
4	Correct	13 ms	3008 KB	Ok
5	Correct	14 ms	3020 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	14 ms	2944 KB	Ok
8	Correct	20 ms	3884 KB	Ok
9	Correct	15 ms	2836 KB	Ok
10	Correct	17 ms	5184 KB	Ok
11	Correct	22 ms	2936 KB	Ok
12	Correct	14 ms	2848 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	5184 KB	Ok
2	Correct	49 ms	5276 KB	Ok
3	Correct	32 ms	5196 KB	Ok
4	Correct	18 ms	5292 KB	Ok
5	Correct	25 ms	5196 KB	Ok
6	Correct	38 ms	5360 KB	Ok
7	Correct	38 ms	5892 KB	Ok
8	Correct	35 ms	5516 KB	Ok
9	Correct	38 ms	5988 KB	Ok
10	Correct	33 ms	5716 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7876 KB	Ok
2	Correct	31 ms	7872 KB	Ok
3	Correct	25 ms	5264 KB	Ok
4	Correct	21 ms	4424 KB	Ok
5	Correct	18 ms	7872 KB	Ok
6	Correct	19 ms	7888 KB	Ok
7	Correct	18 ms	7900 KB	Ok
8	Correct	46 ms	7804 KB	Ok
9	Correct	19 ms	7876 KB	Ok
10	Correct	24 ms	5196 KB	Ok
11	Correct	17 ms	4368 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	5292 KB	Ok
2	Correct	14 ms	3408 KB	Ok
3	Correct	13 ms	3088 KB	Ok
4	Correct	13 ms	3000 KB	Ok
5	Correct	12 ms	2920 KB	Ok
6	Correct	250 ms	11752 KB	Ok
7	Correct	192 ms	12316 KB	Ok
8	Correct	364 ms	15284 KB	Ok
9	Correct	257 ms	13668 KB	Ok
10	Correct	137 ms	7880 KB	Ok
11	Correct	242 ms	13380 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	8000 KB	Ok
2	Correct	38 ms	7884 KB	Ok
3	Correct	46 ms	2996 KB	Ok
4	Correct	13 ms	3008 KB	Ok
5	Correct	14 ms	3020 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	14 ms	2944 KB	Ok
8	Correct	20 ms	3884 KB	Ok
9	Correct	15 ms	2836 KB	Ok
10	Correct	17 ms	5184 KB	Ok
11	Correct	22 ms	2936 KB	Ok
12	Correct	14 ms	2848 KB	Ok
13	Correct	11 ms	7876 KB	Ok
14	Correct	31 ms	7872 KB	Ok
15	Correct	25 ms	5264 KB	Ok
16	Correct	21 ms	4424 KB	Ok
17	Correct	18 ms	7872 KB	Ok
18	Correct	19 ms	7888 KB	Ok
19	Correct	18 ms	7900 KB	Ok
20	Correct	46 ms	7804 KB	Ok
21	Correct	19 ms	7876 KB	Ok
22	Correct	24 ms	5196 KB	Ok
23	Correct	17 ms	4368 KB	Ok
24	Correct	15 ms	2768 KB	Ok
25	Correct	15 ms	2740 KB	Ok
26	Correct	14 ms	2748 KB	Ok
27	Correct	42 ms	2696 KB	Ok
28	Correct	14 ms	2756 KB	Ok
29	Correct	20 ms	2752 KB	Ok
30	Correct	19 ms	2720 KB	Ok
31	Correct	44 ms	2748 KB	Ok
32	Correct	43 ms	2744 KB	Ok
33	Correct	16 ms	2740 KB	Ok
34	Correct	18 ms	2880 KB	Ok
35	Correct	19 ms	2892 KB	Ok
36	Correct	20 ms	2892 KB	Ok
37	Correct	19 ms	2904 KB	Ok
38	Correct	54 ms	2944 KB	Ok
39	Correct	18 ms	2876 KB	Ok
40	Correct	20 ms	2884 KB	Ok
41	Correct	21 ms	2884 KB	Ok
42	Correct	38 ms	2860 KB	Ok
43	Correct	21 ms	2888 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	8000 KB	Ok
2	Correct	38 ms	7884 KB	Ok
3	Correct	46 ms	2996 KB	Ok
4	Correct	13 ms	3008 KB	Ok
5	Correct	14 ms	3020 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	14 ms	2944 KB	Ok
8	Correct	20 ms	3884 KB	Ok
9	Correct	15 ms	2836 KB	Ok
10	Correct	17 ms	5184 KB	Ok
11	Correct	22 ms	2936 KB	Ok
12	Correct	14 ms	2848 KB	Ok
13	Correct	21 ms	5184 KB	Ok
14	Correct	49 ms	5276 KB	Ok
15	Correct	32 ms	5196 KB	Ok
16	Correct	18 ms	5292 KB	Ok
17	Correct	25 ms	5196 KB	Ok
18	Correct	38 ms	5360 KB	Ok
19	Correct	38 ms	5892 KB	Ok
20	Correct	35 ms	5516 KB	Ok
21	Correct	38 ms	5988 KB	Ok
22	Correct	33 ms	5716 KB	Ok
23	Correct	11 ms	7876 KB	Ok
24	Correct	31 ms	7872 KB	Ok
25	Correct	25 ms	5264 KB	Ok
26	Correct	21 ms	4424 KB	Ok
27	Correct	18 ms	7872 KB	Ok
28	Correct	19 ms	7888 KB	Ok
29	Correct	18 ms	7900 KB	Ok
30	Correct	46 ms	7804 KB	Ok
31	Correct	19 ms	7876 KB	Ok
32	Correct	24 ms	5196 KB	Ok
33	Correct	17 ms	4368 KB	Ok
34	Correct	15 ms	2768 KB	Ok
35	Correct	15 ms	2740 KB	Ok
36	Correct	14 ms	2748 KB	Ok
37	Correct	42 ms	2696 KB	Ok
38	Correct	14 ms	2756 KB	Ok
39	Correct	20 ms	2752 KB	Ok
40	Correct	19 ms	2720 KB	Ok
41	Correct	44 ms	2748 KB	Ok
42	Correct	43 ms	2744 KB	Ok
43	Correct	16 ms	2740 KB	Ok
44	Correct	18 ms	2880 KB	Ok
45	Correct	19 ms	2892 KB	Ok
46	Correct	20 ms	2892 KB	Ok
47	Correct	19 ms	2904 KB	Ok
48	Correct	54 ms	2944 KB	Ok
49	Correct	18 ms	2876 KB	Ok
50	Correct	20 ms	2884 KB	Ok
51	Correct	21 ms	2884 KB	Ok
52	Correct	38 ms	2860 KB	Ok
53	Correct	21 ms	2888 KB	Ok
54	Correct	124 ms	5360 KB	Ok
55	Correct	146 ms	5636 KB	Ok
56	Correct	196 ms	5688 KB	Ok
57	Correct	154 ms	4896 KB	Ok
58	Correct	115 ms	5064 KB	Ok
59	Correct	107 ms	4924 KB	Ok
60	Correct	96 ms	4736 KB	Ok
61	Correct	108 ms	4932 KB	Ok
62	Correct	291 ms	5464 KB	Ok
63	Correct	122 ms	5020 KB	Ok
64	Correct	135 ms	5620 KB	Ok
65	Correct	145 ms	5400 KB	Ok
66	Correct	110 ms	5084 KB	Ok
67	Correct	101 ms	5020 KB	Ok
68	Correct	328 ms	5188 KB	Ok
69	Correct	333 ms	12368 KB	Ok
70	Correct	417 ms	12956 KB	Ok
71	Correct	332 ms	12360 KB	Ok
72	Correct	358 ms	12252 KB	Ok
73	Correct	340 ms	12316 KB	Ok
74	Correct	340 ms	12096 KB	Ok
75	Correct	326 ms	11728 KB	Ok
76	Correct	396 ms	12480 KB	Ok
77	Correct	291 ms	11836 KB	Ok
78	Correct	367 ms	12308 KB	Ok
79	Correct	338 ms	12536 KB	Ok
80	Correct	347 ms	12548 KB	Ok
81	Correct	358 ms	12388 KB	Ok
82	Correct	322 ms	12372 KB	Ok
83	Correct	306 ms	11828 KB	Ok

Subtask #7
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	8000 KB	Ok
2	Correct	38 ms	7884 KB	Ok
3	Correct	46 ms	2996 KB	Ok
4	Correct	13 ms	3008 KB	Ok
5	Correct	14 ms	3020 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	14 ms	2944 KB	Ok
8	Correct	20 ms	3884 KB	Ok
9	Correct	15 ms	2836 KB	Ok
10	Correct	17 ms	5184 KB	Ok
11	Correct	22 ms	2936 KB	Ok
12	Correct	14 ms	2848 KB	Ok
13	Correct	21 ms	5184 KB	Ok
14	Correct	49 ms	5276 KB	Ok
15	Correct	32 ms	5196 KB	Ok
16	Correct	18 ms	5292 KB	Ok
17	Correct	25 ms	5196 KB	Ok
18	Correct	38 ms	5360 KB	Ok
19	Correct	38 ms	5892 KB	Ok
20	Correct	35 ms	5516 KB	Ok
21	Correct	38 ms	5988 KB	Ok
22	Correct	33 ms	5716 KB	Ok
23	Correct	11 ms	7876 KB	Ok
24	Correct	31 ms	7872 KB	Ok
25	Correct	25 ms	5264 KB	Ok
26	Correct	21 ms	4424 KB	Ok
27	Correct	18 ms	7872 KB	Ok
28	Correct	19 ms	7888 KB	Ok
29	Correct	18 ms	7900 KB	Ok
30	Correct	46 ms	7804 KB	Ok
31	Correct	19 ms	7876 KB	Ok
32	Correct	24 ms	5196 KB	Ok
33	Correct	17 ms	4368 KB	Ok
34	Correct	30 ms	5292 KB	Ok
35	Correct	14 ms	3408 KB	Ok
36	Correct	13 ms	3088 KB	Ok
37	Correct	13 ms	3000 KB	Ok
38	Correct	12 ms	2920 KB	Ok
39	Correct	250 ms	11752 KB	Ok
40	Correct	192 ms	12316 KB	Ok
41	Correct	364 ms	15284 KB	Ok
42	Correct	257 ms	13668 KB	Ok
43	Correct	137 ms	7880 KB	Ok
44	Correct	242 ms	13380 KB	Ok
45	Correct	15 ms	2768 KB	Ok
46	Correct	15 ms	2740 KB	Ok
47	Correct	14 ms	2748 KB	Ok
48	Correct	42 ms	2696 KB	Ok
49	Correct	14 ms	2756 KB	Ok
50	Correct	20 ms	2752 KB	Ok
51	Correct	19 ms	2720 KB	Ok
52	Correct	44 ms	2748 KB	Ok
53	Correct	43 ms	2744 KB	Ok
54	Correct	16 ms	2740 KB	Ok
55	Correct	18 ms	2880 KB	Ok
56	Correct	19 ms	2892 KB	Ok
57	Correct	20 ms	2892 KB	Ok
58	Correct	19 ms	2904 KB	Ok
59	Correct	54 ms	2944 KB	Ok
60	Correct	18 ms	2876 KB	Ok
61	Correct	20 ms	2884 KB	Ok
62	Correct	21 ms	2884 KB	Ok
63	Correct	38 ms	2860 KB	Ok
64	Correct	21 ms	2888 KB	Ok
65	Correct	124 ms	5360 KB	Ok
66	Correct	146 ms	5636 KB	Ok
67	Correct	196 ms	5688 KB	Ok
68	Correct	154 ms	4896 KB	Ok
69	Correct	115 ms	5064 KB	Ok
70	Correct	107 ms	4924 KB	Ok
71	Correct	96 ms	4736 KB	Ok
72	Correct	108 ms	4932 KB	Ok
73	Correct	291 ms	5464 KB	Ok
74	Correct	122 ms	5020 KB	Ok
75	Correct	135 ms	5620 KB	Ok
76	Correct	145 ms	5400 KB	Ok
77	Correct	110 ms	5084 KB	Ok
78	Correct	101 ms	5020 KB	Ok
79	Correct	328 ms	5188 KB	Ok
80	Correct	333 ms	12368 KB	Ok
81	Correct	417 ms	12956 KB	Ok
82	Correct	332 ms	12360 KB	Ok
83	Correct	358 ms	12252 KB	Ok
84	Correct	340 ms	12316 KB	Ok
85	Correct	340 ms	12096 KB	Ok
86	Correct	326 ms	11728 KB	Ok
87	Correct	396 ms	12480 KB	Ok
88	Correct	291 ms	11836 KB	Ok
89	Correct	367 ms	12308 KB	Ok
90	Correct	338 ms	12536 KB	Ok
91	Correct	347 ms	12548 KB	Ok
92	Correct	358 ms	12388 KB	Ok
93	Correct	322 ms	12372 KB	Ok
94	Correct	306 ms	11828 KB	Ok
95	Correct	284 ms	9980 KB	Ok
96	Correct	394 ms	13116 KB	Ok
97	Correct	372 ms	11112 KB	Ok
98	Correct	286 ms	10776 KB	Ok
99	Correct	312 ms	10524 KB	Ok
100	Correct	371 ms	10732 KB	Ok
101	Correct	382 ms	11800 KB	Ok
102	Correct	388 ms	10952 KB	Ok
103	Correct	328 ms	11688 KB	Ok
104	Correct	394 ms	13012 KB	Ok
105	Correct	367 ms	12944 KB	Ok
106	Correct	309 ms	12740 KB	Ok
107	Correct	357 ms	12280 KB	Ok
108	Correct	439 ms	12992 KB	Ok
109	Correct	451 ms	13320 KB	Ok
110	Correct	1582 ms	43504 KB	Ok
111	Correct	1922 ms	46280 KB	Ok
112	Correct	1734 ms	46336 KB	Ok
113	Correct	1626 ms	45644 KB	Ok
114	Correct	1602 ms	47544 KB	Ok
115	Correct	1803 ms	45296 KB	Ok
116	Correct	1707 ms	46676 KB	Ok
117	Correct	1876 ms	45072 KB	Ok
118	Correct	1530 ms	45208 KB	Ok
119	Correct	1849 ms	45184 KB	Ok
120	Correct	1767 ms	44876 KB	Ok
121	Correct	1625 ms	43824 KB	Ok
122	Correct	1667 ms	46104 KB	Ok
123	Correct	1791 ms	46380 KB	Ok
124	Correct	1507 ms	43832 KB	Ok
125	Correct	960 ms	29044 KB	Ok

답안 #496583

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 9.0 / 9.0

Subtask #3 14.0 / 14.0

Subtask #4 15.0 / 15.0

Subtask #5 14.0 / 14.0

Subtask #6 18.0 / 18.0

Subtask #7 24.0 / 24.0

Subtask #1
6.0 / 6.0

Subtask #2
9.0 / 9.0

Subtask #3
14.0 / 14.0

Subtask #4
15.0 / 15.0

Subtask #5
14.0 / 14.0

Subtask #6
18.0 / 18.0

Subtask #7
24.0 / 24.0