답안 #496578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496578	2021-12-21T14:55:21 Z	vinnipuh01	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2000 ms	41668 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	22 ms	7884 KB	Ok
2	Correct	21 ms	7876 KB	Ok
3	Correct	13 ms	3020 KB	Ok
4	Correct	12 ms	3020 KB	Ok
5	Correct	12 ms	3052 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	12 ms	2940 KB	Ok
8	Correct	13 ms	3916 KB	Ok
9	Correct	12 ms	2764 KB	Ok
10	Correct	14 ms	5196 KB	Ok
11	Correct	13 ms	2892 KB	Ok
12	Correct	12 ms	2844 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	5296 KB	Ok
2	Correct	15 ms	5288 KB	Ok
3	Correct	18 ms	5196 KB	Ok
4	Correct	16 ms	5284 KB	Ok
5	Correct	16 ms	5284 KB	Ok
6	Correct	19 ms	5324 KB	Ok
7	Correct	31 ms	5952 KB	Ok
8	Correct	27 ms	5576 KB	Ok
9	Correct	33 ms	5964 KB	Ok
10	Correct	28 ms	5708 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7884 KB	Ok
2	Correct	28 ms	7900 KB	Ok
3	Correct	23 ms	5288 KB	Ok
4	Correct	18 ms	4424 KB	Ok
5	Correct	19 ms	7896 KB	Ok
6	Correct	20 ms	7820 KB	Ok
7	Correct	19 ms	7900 KB	Ok
8	Correct	19 ms	7824 KB	Ok
9	Correct	17 ms	7896 KB	Ok
10	Correct	15 ms	5188 KB	Ok
11	Correct	14 ms	4300 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	5288 KB	Ok
2	Correct	14 ms	3424 KB	Ok
3	Correct	13 ms	3080 KB	Ok
4	Correct	13 ms	2988 KB	Ok
5	Correct	13 ms	2892 KB	Ok
6	Correct	190 ms	11840 KB	Ok
7	Correct	180 ms	12272 KB	Ok
8	Correct	318 ms	15300 KB	Ok
9	Correct	235 ms	13636 KB	Ok
10	Correct	128 ms	7804 KB	Ok
11	Correct	209 ms	13380 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	7884 KB	Ok
2	Correct	21 ms	7876 KB	Ok
3	Correct	13 ms	3020 KB	Ok
4	Correct	12 ms	3020 KB	Ok
5	Correct	12 ms	3052 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	12 ms	2940 KB	Ok
8	Correct	13 ms	3916 KB	Ok
9	Correct	12 ms	2764 KB	Ok
10	Correct	14 ms	5196 KB	Ok
11	Correct	13 ms	2892 KB	Ok
12	Correct	12 ms	2844 KB	Ok
13	Correct	9 ms	7884 KB	Ok
14	Correct	28 ms	7900 KB	Ok
15	Correct	23 ms	5288 KB	Ok
16	Correct	18 ms	4424 KB	Ok
17	Correct	19 ms	7896 KB	Ok
18	Correct	20 ms	7820 KB	Ok
19	Correct	19 ms	7900 KB	Ok
20	Correct	19 ms	7824 KB	Ok
21	Correct	17 ms	7896 KB	Ok
22	Correct	15 ms	5188 KB	Ok
23	Correct	14 ms	4300 KB	Ok
24	Correct	15 ms	2764 KB	Ok
25	Correct	14 ms	2744 KB	Ok
26	Correct	13 ms	2744 KB	Ok
27	Correct	14 ms	2748 KB	Ok
28	Correct	15 ms	2720 KB	Ok
29	Correct	14 ms	2772 KB	Ok
30	Correct	12 ms	2636 KB	Ok
31	Correct	14 ms	2764 KB	Ok
32	Correct	13 ms	2764 KB	Ok
33	Correct	13 ms	2764 KB	Ok
34	Correct	17 ms	2896 KB	Ok
35	Correct	20 ms	2960 KB	Ok
36	Correct	18 ms	2872 KB	Ok
37	Correct	19 ms	2940 KB	Ok
38	Correct	19 ms	2892 KB	Ok
39	Correct	19 ms	2880 KB	Ok
40	Correct	20 ms	2920 KB	Ok
41	Correct	18 ms	2896 KB	Ok
42	Correct	19 ms	2928 KB	Ok
43	Correct	19 ms	2892 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	7884 KB	Ok
2	Correct	21 ms	7876 KB	Ok
3	Correct	13 ms	3020 KB	Ok
4	Correct	12 ms	3020 KB	Ok
5	Correct	12 ms	3052 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	12 ms	2940 KB	Ok
8	Correct	13 ms	3916 KB	Ok
9	Correct	12 ms	2764 KB	Ok
10	Correct	14 ms	5196 KB	Ok
11	Correct	13 ms	2892 KB	Ok
12	Correct	12 ms	2844 KB	Ok
13	Correct	18 ms	5296 KB	Ok
14	Correct	15 ms	5288 KB	Ok
15	Correct	18 ms	5196 KB	Ok
16	Correct	16 ms	5284 KB	Ok
17	Correct	16 ms	5284 KB	Ok
18	Correct	19 ms	5324 KB	Ok
19	Correct	31 ms	5952 KB	Ok
20	Correct	27 ms	5576 KB	Ok
21	Correct	33 ms	5964 KB	Ok
22	Correct	28 ms	5708 KB	Ok
23	Correct	9 ms	7884 KB	Ok
24	Correct	28 ms	7900 KB	Ok
25	Correct	23 ms	5288 KB	Ok
26	Correct	18 ms	4424 KB	Ok
27	Correct	19 ms	7896 KB	Ok
28	Correct	20 ms	7820 KB	Ok
29	Correct	19 ms	7900 KB	Ok
30	Correct	19 ms	7824 KB	Ok
31	Correct	17 ms	7896 KB	Ok
32	Correct	15 ms	5188 KB	Ok
33	Correct	14 ms	4300 KB	Ok
34	Correct	15 ms	2764 KB	Ok
35	Correct	14 ms	2744 KB	Ok
36	Correct	13 ms	2744 KB	Ok
37	Correct	14 ms	2748 KB	Ok
38	Correct	15 ms	2720 KB	Ok
39	Correct	14 ms	2772 KB	Ok
40	Correct	12 ms	2636 KB	Ok
41	Correct	14 ms	2764 KB	Ok
42	Correct	13 ms	2764 KB	Ok
43	Correct	13 ms	2764 KB	Ok
44	Correct	17 ms	2896 KB	Ok
45	Correct	20 ms	2960 KB	Ok
46	Correct	18 ms	2872 KB	Ok
47	Correct	19 ms	2940 KB	Ok
48	Correct	19 ms	2892 KB	Ok
49	Correct	19 ms	2880 KB	Ok
50	Correct	20 ms	2920 KB	Ok
51	Correct	18 ms	2896 KB	Ok
52	Correct	19 ms	2928 KB	Ok
53	Correct	19 ms	2892 KB	Ok
54	Correct	111 ms	5248 KB	Ok
55	Correct	132 ms	5592 KB	Ok
56	Correct	131 ms	5628 KB	Ok
57	Correct	93 ms	4824 KB	Ok
58	Correct	117 ms	5124 KB	Ok
59	Correct	105 ms	4888 KB	Ok
60	Correct	90 ms	4704 KB	Ok
61	Correct	95 ms	4932 KB	Ok
62	Correct	123 ms	5332 KB	Ok
63	Correct	101 ms	5044 KB	Ok
64	Correct	142 ms	5696 KB	Ok
65	Correct	123 ms	5296 KB	Ok
66	Correct	109 ms	5080 KB	Ok
67	Correct	95 ms	4964 KB	Ok
68	Correct	131 ms	5124 KB	Ok
69	Correct	305 ms	12236 KB	Ok
70	Correct	374 ms	12972 KB	Ok
71	Correct	309 ms	12412 KB	Ok
72	Correct	338 ms	12352 KB	Ok
73	Correct	341 ms	12300 KB	Ok
74	Correct	306 ms	12132 KB	Ok
75	Correct	337 ms	11808 KB	Ok
76	Correct	367 ms	12612 KB	Ok
77	Correct	287 ms	11760 KB	Ok
78	Correct	376 ms	12376 KB	Ok
79	Correct	341 ms	12428 KB	Ok
80	Correct	318 ms	12496 KB	Ok
81	Correct	342 ms	12380 KB	Ok
82	Correct	313 ms	12368 KB	Ok
83	Correct	285 ms	11852 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	7884 KB	Ok
2	Correct	21 ms	7876 KB	Ok
3	Correct	13 ms	3020 KB	Ok
4	Correct	12 ms	3020 KB	Ok
5	Correct	12 ms	3052 KB	Ok
6	Correct	13 ms	3916 KB	Ok
7	Correct	12 ms	2940 KB	Ok
8	Correct	13 ms	3916 KB	Ok
9	Correct	12 ms	2764 KB	Ok
10	Correct	14 ms	5196 KB	Ok
11	Correct	13 ms	2892 KB	Ok
12	Correct	12 ms	2844 KB	Ok
13	Correct	18 ms	5296 KB	Ok
14	Correct	15 ms	5288 KB	Ok
15	Correct	18 ms	5196 KB	Ok
16	Correct	16 ms	5284 KB	Ok
17	Correct	16 ms	5284 KB	Ok
18	Correct	19 ms	5324 KB	Ok
19	Correct	31 ms	5952 KB	Ok
20	Correct	27 ms	5576 KB	Ok
21	Correct	33 ms	5964 KB	Ok
22	Correct	28 ms	5708 KB	Ok
23	Correct	9 ms	7884 KB	Ok
24	Correct	28 ms	7900 KB	Ok
25	Correct	23 ms	5288 KB	Ok
26	Correct	18 ms	4424 KB	Ok
27	Correct	19 ms	7896 KB	Ok
28	Correct	20 ms	7820 KB	Ok
29	Correct	19 ms	7900 KB	Ok
30	Correct	19 ms	7824 KB	Ok
31	Correct	17 ms	7896 KB	Ok
32	Correct	15 ms	5188 KB	Ok
33	Correct	14 ms	4300 KB	Ok
34	Correct	16 ms	5288 KB	Ok
35	Correct	14 ms	3424 KB	Ok
36	Correct	13 ms	3080 KB	Ok
37	Correct	13 ms	2988 KB	Ok
38	Correct	13 ms	2892 KB	Ok
39	Correct	190 ms	11840 KB	Ok
40	Correct	180 ms	12272 KB	Ok
41	Correct	318 ms	15300 KB	Ok
42	Correct	235 ms	13636 KB	Ok
43	Correct	128 ms	7804 KB	Ok
44	Correct	209 ms	13380 KB	Ok
45	Correct	15 ms	2764 KB	Ok
46	Correct	14 ms	2744 KB	Ok
47	Correct	13 ms	2744 KB	Ok
48	Correct	14 ms	2748 KB	Ok
49	Correct	15 ms	2720 KB	Ok
50	Correct	14 ms	2772 KB	Ok
51	Correct	12 ms	2636 KB	Ok
52	Correct	14 ms	2764 KB	Ok
53	Correct	13 ms	2764 KB	Ok
54	Correct	13 ms	2764 KB	Ok
55	Correct	17 ms	2896 KB	Ok
56	Correct	20 ms	2960 KB	Ok
57	Correct	18 ms	2872 KB	Ok
58	Correct	19 ms	2940 KB	Ok
59	Correct	19 ms	2892 KB	Ok
60	Correct	19 ms	2880 KB	Ok
61	Correct	20 ms	2920 KB	Ok
62	Correct	18 ms	2896 KB	Ok
63	Correct	19 ms	2928 KB	Ok
64	Correct	19 ms	2892 KB	Ok
65	Correct	111 ms	5248 KB	Ok
66	Correct	132 ms	5592 KB	Ok
67	Correct	131 ms	5628 KB	Ok
68	Correct	93 ms	4824 KB	Ok
69	Correct	117 ms	5124 KB	Ok
70	Correct	105 ms	4888 KB	Ok
71	Correct	90 ms	4704 KB	Ok
72	Correct	95 ms	4932 KB	Ok
73	Correct	123 ms	5332 KB	Ok
74	Correct	101 ms	5044 KB	Ok
75	Correct	142 ms	5696 KB	Ok
76	Correct	123 ms	5296 KB	Ok
77	Correct	109 ms	5080 KB	Ok
78	Correct	95 ms	4964 KB	Ok
79	Correct	131 ms	5124 KB	Ok
80	Correct	305 ms	12236 KB	Ok
81	Correct	374 ms	12972 KB	Ok
82	Correct	309 ms	12412 KB	Ok
83	Correct	338 ms	12352 KB	Ok
84	Correct	341 ms	12300 KB	Ok
85	Correct	306 ms	12132 KB	Ok
86	Correct	337 ms	11808 KB	Ok
87	Correct	367 ms	12612 KB	Ok
88	Correct	287 ms	11760 KB	Ok
89	Correct	376 ms	12376 KB	Ok
90	Correct	341 ms	12428 KB	Ok
91	Correct	318 ms	12496 KB	Ok
92	Correct	342 ms	12380 KB	Ok
93	Correct	313 ms	12368 KB	Ok
94	Correct	285 ms	11852 KB	Ok
95	Correct	269 ms	9916 KB	Ok
96	Correct	386 ms	13080 KB	Ok
97	Correct	356 ms	11220 KB	Ok
98	Correct	305 ms	10808 KB	Ok
99	Correct	327 ms	10576 KB	Ok
100	Correct	360 ms	10780 KB	Ok
101	Correct	351 ms	11824 KB	Ok
102	Correct	339 ms	11076 KB	Ok
103	Correct	364 ms	11696 KB	Ok
104	Correct	417 ms	13012 KB	Ok
105	Correct	397 ms	12972 KB	Ok
106	Correct	324 ms	12712 KB	Ok
107	Correct	353 ms	12188 KB	Ok
108	Correct	434 ms	12896 KB	Ok
109	Correct	404 ms	13312 KB	Ok
110	Execution timed out	2061 ms	41668 KB	Time limit exceeded
111	Halted	0 ms	0 KB	-

답안 #496578

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 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
0 / 24.0