답안 #496576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496576	2021-12-21T14:51:23 Z	vinnipuh01	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2000 ms	45796 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;
 
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;
}
 
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	27 ms	8908 KB	Ok
2	Correct	29 ms	8908 KB	Ok
3	Correct	19 ms	3148 KB	Ok
4	Correct	23 ms	3032 KB	Ok
5	Correct	19 ms	3124 KB	Ok
6	Correct	19 ms	4172 KB	Ok
7	Correct	18 ms	2892 KB	Ok
8	Correct	20 ms	4240 KB	Ok
9	Correct	18 ms	2764 KB	Ok
10	Correct	20 ms	5708 KB	Ok
11	Correct	19 ms	2992 KB	Ok
12	Correct	18 ms	2764 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	5708 KB	Ok
2	Correct	24 ms	5808 KB	Ok
3	Correct	23 ms	5708 KB	Ok
4	Correct	21 ms	5708 KB	Ok
5	Correct	23 ms	5812 KB	Ok
6	Correct	28 ms	5924 KB	Ok
7	Correct	39 ms	6468 KB	Ok
8	Correct	32 ms	6088 KB	Ok
9	Correct	40 ms	6596 KB	Ok
10	Correct	41 ms	6300 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8908 KB	Ok
2	Correct	30 ms	8908 KB	Ok
3	Correct	26 ms	5792 KB	Ok
4	Correct	23 ms	4772 KB	Ok
5	Correct	32 ms	8924 KB	Ok
6	Correct	24 ms	8856 KB	Ok
7	Correct	23 ms	8908 KB	Ok
8	Correct	30 ms	8848 KB	Ok
9	Correct	23 ms	8884 KB	Ok
10	Correct	22 ms	5792 KB	Ok
11	Correct	21 ms	4684 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	5808 KB	Ok
2	Correct	21 ms	3572 KB	Ok
3	Correct	21 ms	3160 KB	Ok
4	Correct	22 ms	3048 KB	Ok
5	Correct	21 ms	2960 KB	Ok
6	Correct	213 ms	12688 KB	Ok
7	Correct	242 ms	13020 KB	Ok
8	Correct	411 ms	16036 KB	Ok
9	Correct	303 ms	14408 KB	Ok
10	Correct	153 ms	8408 KB	Ok
11	Correct	257 ms	14552 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	8908 KB	Ok
2	Correct	29 ms	8908 KB	Ok
3	Correct	19 ms	3148 KB	Ok
4	Correct	23 ms	3032 KB	Ok
5	Correct	19 ms	3124 KB	Ok
6	Correct	19 ms	4172 KB	Ok
7	Correct	18 ms	2892 KB	Ok
8	Correct	20 ms	4240 KB	Ok
9	Correct	18 ms	2764 KB	Ok
10	Correct	20 ms	5708 KB	Ok
11	Correct	19 ms	2992 KB	Ok
12	Correct	18 ms	2764 KB	Ok
13	Correct	13 ms	8908 KB	Ok
14	Correct	30 ms	8908 KB	Ok
15	Correct	26 ms	5792 KB	Ok
16	Correct	23 ms	4772 KB	Ok
17	Correct	32 ms	8924 KB	Ok
18	Correct	24 ms	8856 KB	Ok
19	Correct	23 ms	8908 KB	Ok
20	Correct	30 ms	8848 KB	Ok
21	Correct	23 ms	8884 KB	Ok
22	Correct	22 ms	5792 KB	Ok
23	Correct	21 ms	4684 KB	Ok
24	Correct	21 ms	2748 KB	Ok
25	Correct	22 ms	2736 KB	Ok
26	Correct	21 ms	2740 KB	Ok
27	Correct	20 ms	2764 KB	Ok
28	Correct	19 ms	2764 KB	Ok
29	Correct	19 ms	2776 KB	Ok
30	Correct	20 ms	2688 KB	Ok
31	Correct	20 ms	2712 KB	Ok
32	Correct	24 ms	2828 KB	Ok
33	Correct	22 ms	2752 KB	Ok
34	Correct	26 ms	2900 KB	Ok
35	Correct	26 ms	2960 KB	Ok
36	Correct	25 ms	2948 KB	Ok
37	Correct	27 ms	2916 KB	Ok
38	Correct	24 ms	2896 KB	Ok
39	Correct	25 ms	2892 KB	Ok
40	Correct	35 ms	2892 KB	Ok
41	Correct	26 ms	2892 KB	Ok
42	Correct	25 ms	2904 KB	Ok
43	Correct	26 ms	2932 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	8908 KB	Ok
2	Correct	29 ms	8908 KB	Ok
3	Correct	19 ms	3148 KB	Ok
4	Correct	23 ms	3032 KB	Ok
5	Correct	19 ms	3124 KB	Ok
6	Correct	19 ms	4172 KB	Ok
7	Correct	18 ms	2892 KB	Ok
8	Correct	20 ms	4240 KB	Ok
9	Correct	18 ms	2764 KB	Ok
10	Correct	20 ms	5708 KB	Ok
11	Correct	19 ms	2992 KB	Ok
12	Correct	18 ms	2764 KB	Ok
13	Correct	23 ms	5708 KB	Ok
14	Correct	24 ms	5808 KB	Ok
15	Correct	23 ms	5708 KB	Ok
16	Correct	21 ms	5708 KB	Ok
17	Correct	23 ms	5812 KB	Ok
18	Correct	28 ms	5924 KB	Ok
19	Correct	39 ms	6468 KB	Ok
20	Correct	32 ms	6088 KB	Ok
21	Correct	40 ms	6596 KB	Ok
22	Correct	41 ms	6300 KB	Ok
23	Correct	13 ms	8908 KB	Ok
24	Correct	30 ms	8908 KB	Ok
25	Correct	26 ms	5792 KB	Ok
26	Correct	23 ms	4772 KB	Ok
27	Correct	32 ms	8924 KB	Ok
28	Correct	24 ms	8856 KB	Ok
29	Correct	23 ms	8908 KB	Ok
30	Correct	30 ms	8848 KB	Ok
31	Correct	23 ms	8884 KB	Ok
32	Correct	22 ms	5792 KB	Ok
33	Correct	21 ms	4684 KB	Ok
34	Correct	21 ms	2748 KB	Ok
35	Correct	22 ms	2736 KB	Ok
36	Correct	21 ms	2740 KB	Ok
37	Correct	20 ms	2764 KB	Ok
38	Correct	19 ms	2764 KB	Ok
39	Correct	19 ms	2776 KB	Ok
40	Correct	20 ms	2688 KB	Ok
41	Correct	20 ms	2712 KB	Ok
42	Correct	24 ms	2828 KB	Ok
43	Correct	22 ms	2752 KB	Ok
44	Correct	26 ms	2900 KB	Ok
45	Correct	26 ms	2960 KB	Ok
46	Correct	25 ms	2948 KB	Ok
47	Correct	27 ms	2916 KB	Ok
48	Correct	24 ms	2896 KB	Ok
49	Correct	25 ms	2892 KB	Ok
50	Correct	35 ms	2892 KB	Ok
51	Correct	26 ms	2892 KB	Ok
52	Correct	25 ms	2904 KB	Ok
53	Correct	26 ms	2932 KB	Ok
54	Correct	172 ms	5304 KB	Ok
55	Correct	168 ms	5612 KB	Ok
56	Correct	164 ms	5620 KB	Ok
57	Correct	113 ms	4920 KB	Ok
58	Correct	145 ms	5048 KB	Ok
59	Correct	124 ms	4980 KB	Ok
60	Correct	115 ms	4876 KB	Ok
61	Correct	122 ms	4856 KB	Ok
62	Correct	148 ms	5356 KB	Ok
63	Correct	130 ms	5060 KB	Ok
64	Correct	161 ms	5700 KB	Ok
65	Correct	135 ms	5220 KB	Ok
66	Correct	137 ms	5028 KB	Ok
67	Correct	120 ms	4932 KB	Ok
68	Correct	134 ms	5264 KB	Ok
69	Correct	365 ms	12872 KB	Ok
70	Correct	428 ms	13396 KB	Ok
71	Correct	356 ms	12852 KB	Ok
72	Correct	366 ms	12740 KB	Ok
73	Correct	366 ms	12868 KB	Ok
74	Correct	342 ms	12868 KB	Ok
75	Correct	359 ms	12316 KB	Ok
76	Correct	415 ms	13044 KB	Ok
77	Correct	321 ms	12356 KB	Ok
78	Correct	405 ms	12980 KB	Ok
79	Correct	385 ms	13032 KB	Ok
80	Correct	363 ms	13148 KB	Ok
81	Correct	380 ms	12900 KB	Ok
82	Correct	374 ms	12872 KB	Ok
83	Correct	342 ms	12468 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	8908 KB	Ok
2	Correct	29 ms	8908 KB	Ok
3	Correct	19 ms	3148 KB	Ok
4	Correct	23 ms	3032 KB	Ok
5	Correct	19 ms	3124 KB	Ok
6	Correct	19 ms	4172 KB	Ok
7	Correct	18 ms	2892 KB	Ok
8	Correct	20 ms	4240 KB	Ok
9	Correct	18 ms	2764 KB	Ok
10	Correct	20 ms	5708 KB	Ok
11	Correct	19 ms	2992 KB	Ok
12	Correct	18 ms	2764 KB	Ok
13	Correct	23 ms	5708 KB	Ok
14	Correct	24 ms	5808 KB	Ok
15	Correct	23 ms	5708 KB	Ok
16	Correct	21 ms	5708 KB	Ok
17	Correct	23 ms	5812 KB	Ok
18	Correct	28 ms	5924 KB	Ok
19	Correct	39 ms	6468 KB	Ok
20	Correct	32 ms	6088 KB	Ok
21	Correct	40 ms	6596 KB	Ok
22	Correct	41 ms	6300 KB	Ok
23	Correct	13 ms	8908 KB	Ok
24	Correct	30 ms	8908 KB	Ok
25	Correct	26 ms	5792 KB	Ok
26	Correct	23 ms	4772 KB	Ok
27	Correct	32 ms	8924 KB	Ok
28	Correct	24 ms	8856 KB	Ok
29	Correct	23 ms	8908 KB	Ok
30	Correct	30 ms	8848 KB	Ok
31	Correct	23 ms	8884 KB	Ok
32	Correct	22 ms	5792 KB	Ok
33	Correct	21 ms	4684 KB	Ok
34	Correct	21 ms	5808 KB	Ok
35	Correct	21 ms	3572 KB	Ok
36	Correct	21 ms	3160 KB	Ok
37	Correct	22 ms	3048 KB	Ok
38	Correct	21 ms	2960 KB	Ok
39	Correct	213 ms	12688 KB	Ok
40	Correct	242 ms	13020 KB	Ok
41	Correct	411 ms	16036 KB	Ok
42	Correct	303 ms	14408 KB	Ok
43	Correct	153 ms	8408 KB	Ok
44	Correct	257 ms	14552 KB	Ok
45	Correct	21 ms	2748 KB	Ok
46	Correct	22 ms	2736 KB	Ok
47	Correct	21 ms	2740 KB	Ok
48	Correct	20 ms	2764 KB	Ok
49	Correct	19 ms	2764 KB	Ok
50	Correct	19 ms	2776 KB	Ok
51	Correct	20 ms	2688 KB	Ok
52	Correct	20 ms	2712 KB	Ok
53	Correct	24 ms	2828 KB	Ok
54	Correct	22 ms	2752 KB	Ok
55	Correct	26 ms	2900 KB	Ok
56	Correct	26 ms	2960 KB	Ok
57	Correct	25 ms	2948 KB	Ok
58	Correct	27 ms	2916 KB	Ok
59	Correct	24 ms	2896 KB	Ok
60	Correct	25 ms	2892 KB	Ok
61	Correct	35 ms	2892 KB	Ok
62	Correct	26 ms	2892 KB	Ok
63	Correct	25 ms	2904 KB	Ok
64	Correct	26 ms	2932 KB	Ok
65	Correct	172 ms	5304 KB	Ok
66	Correct	168 ms	5612 KB	Ok
67	Correct	164 ms	5620 KB	Ok
68	Correct	113 ms	4920 KB	Ok
69	Correct	145 ms	5048 KB	Ok
70	Correct	124 ms	4980 KB	Ok
71	Correct	115 ms	4876 KB	Ok
72	Correct	122 ms	4856 KB	Ok
73	Correct	148 ms	5356 KB	Ok
74	Correct	130 ms	5060 KB	Ok
75	Correct	161 ms	5700 KB	Ok
76	Correct	135 ms	5220 KB	Ok
77	Correct	137 ms	5028 KB	Ok
78	Correct	120 ms	4932 KB	Ok
79	Correct	134 ms	5264 KB	Ok
80	Correct	365 ms	12872 KB	Ok
81	Correct	428 ms	13396 KB	Ok
82	Correct	356 ms	12852 KB	Ok
83	Correct	366 ms	12740 KB	Ok
84	Correct	366 ms	12868 KB	Ok
85	Correct	342 ms	12868 KB	Ok
86	Correct	359 ms	12316 KB	Ok
87	Correct	415 ms	13044 KB	Ok
88	Correct	321 ms	12356 KB	Ok
89	Correct	405 ms	12980 KB	Ok
90	Correct	385 ms	13032 KB	Ok
91	Correct	363 ms	13148 KB	Ok
92	Correct	380 ms	12900 KB	Ok
93	Correct	374 ms	12872 KB	Ok
94	Correct	342 ms	12468 KB	Ok
95	Correct	333 ms	9940 KB	Ok
96	Correct	464 ms	13036 KB	Ok
97	Correct	444 ms	11096 KB	Ok
98	Correct	319 ms	10824 KB	Ok
99	Correct	390 ms	10684 KB	Ok
100	Correct	427 ms	10716 KB	Ok
101	Correct	431 ms	11800 KB	Ok
102	Correct	406 ms	10984 KB	Ok
103	Correct	397 ms	11724 KB	Ok
104	Correct	462 ms	12948 KB	Ok
105	Correct	446 ms	12944 KB	Ok
106	Correct	391 ms	12672 KB	Ok
107	Correct	439 ms	12320 KB	Ok
108	Correct	501 ms	12972 KB	Ok
109	Correct	478 ms	13336 KB	Ok
110	Correct	1802 ms	45732 KB	Ok
111	Execution timed out	2086 ms	45796 KB	Time limit exceeded
112	Halted	0 ms	0 KB	-

답안 #496576

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