답안 #42939 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42939	2018-03-06T11:29:33 Z	bash	Nice sequence (IZhO18_sequence)	C++14	100 / 100	713 ms	43236 KB

sequence

/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <bits/stdc++.h>

#define F first
#define S second
#define endl '\n'
#define pb push_back

const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;
using namespace std;

typedef long long ll;

long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}

int N, M, sz;
int a[MAXN];
int used[MAXN];
int timer;
int tmr = 1;

void dfs(int v) {

    used[v] = tmr;
    if (v - N >= 0 && used[v-N] != tmr)
    	dfs(v - N);
    if (v + M <= sz && used[v+M] != tmr)
    	dfs(v + M);
    a[v] = timer++;
} 

int main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int T = readInt();
    while(T--) {
	    N = readInt(), M = readInt();
	    sz = N + M - __gcd(N, M) - 1;
	    timer = 0;
	    tmr ++;
	    cout << sz << endl;
		for (int i = 0; i <= sz; i++) {
			if (used[i] != tmr)
			dfs(i);
		}    
		for (int i = 0; i < sz; i++) {
			cout << a[i] - a[i+1] << ' ';
		}
		cout << endl;

	}
    return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Ok
2	Correct	1 ms	352 KB	Ok
3	Correct	1 ms	404 KB	Ok
4	Correct	1 ms	476 KB	Ok
5	Correct	1 ms	476 KB	Ok
6	Correct	1 ms	532 KB	Ok
7	Correct	2 ms	536 KB	Ok
8	Correct	1 ms	656 KB	Ok
9	Correct	1 ms	656 KB	Ok
10	Correct	1 ms	656 KB	Ok
11	Correct	1 ms	656 KB	Ok
12	Correct	1 ms	656 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	656 KB	Ok
2	Correct	2 ms	656 KB	Ok
3	Correct	2 ms	724 KB	Ok
4	Correct	2 ms	724 KB	Ok
5	Correct	1 ms	724 KB	Ok
6	Correct	3 ms	812 KB	Ok
7	Correct	10 ms	1216 KB	Ok
8	Correct	5 ms	1216 KB	Ok
9	Correct	11 ms	1416 KB	Ok
10	Correct	7 ms	1416 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1416 KB	Ok
2	Correct	1 ms	1416 KB	Ok
3	Correct	1 ms	1416 KB	Ok
4	Correct	1 ms	1416 KB	Ok
5	Correct	1 ms	1416 KB	Ok
6	Correct	1 ms	1416 KB	Ok
7	Correct	1 ms	1416 KB	Ok
8	Correct	1 ms	1416 KB	Ok
9	Correct	1 ms	1416 KB	Ok
10	Correct	1 ms	1416 KB	Ok
11	Correct	1 ms	1416 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1416 KB	Ok
2	Correct	1 ms	1416 KB	Ok
3	Correct	1 ms	1416 KB	Ok
4	Correct	1 ms	1416 KB	Ok
5	Correct	1 ms	1416 KB	Ok
6	Correct	82 ms	10232 KB	Ok
7	Correct	74 ms	10232 KB	Ok
8	Correct	156 ms	12016 KB	Ok
9	Correct	113 ms	12016 KB	Ok
10	Correct	66 ms	12016 KB	Ok
11	Correct	124 ms	13252 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Ok
2	Correct	1 ms	352 KB	Ok
3	Correct	1 ms	404 KB	Ok
4	Correct	1 ms	476 KB	Ok
5	Correct	1 ms	476 KB	Ok
6	Correct	1 ms	532 KB	Ok
7	Correct	2 ms	536 KB	Ok
8	Correct	1 ms	656 KB	Ok
9	Correct	1 ms	656 KB	Ok
10	Correct	1 ms	656 KB	Ok
11	Correct	1 ms	656 KB	Ok
12	Correct	1 ms	656 KB	Ok
13	Correct	1 ms	1416 KB	Ok
14	Correct	1 ms	1416 KB	Ok
15	Correct	1 ms	1416 KB	Ok
16	Correct	1 ms	1416 KB	Ok
17	Correct	1 ms	1416 KB	Ok
18	Correct	1 ms	1416 KB	Ok
19	Correct	1 ms	1416 KB	Ok
20	Correct	1 ms	1416 KB	Ok
21	Correct	1 ms	1416 KB	Ok
22	Correct	1 ms	1416 KB	Ok
23	Correct	1 ms	1416 KB	Ok
24	Correct	4 ms	13252 KB	Ok
25	Correct	5 ms	13252 KB	Ok
26	Correct	3 ms	13252 KB	Ok
27	Correct	3 ms	13252 KB	Ok
28	Correct	3 ms	13252 KB	Ok
29	Correct	5 ms	13252 KB	Ok
30	Correct	3 ms	13252 KB	Ok
31	Correct	3 ms	13252 KB	Ok
32	Correct	3 ms	13252 KB	Ok
33	Correct	5 ms	13252 KB	Ok
34	Correct	5 ms	13252 KB	Ok
35	Correct	5 ms	13252 KB	Ok
36	Correct	5 ms	13252 KB	Ok
37	Correct	5 ms	13252 KB	Ok
38	Correct	5 ms	13252 KB	Ok
39	Correct	5 ms	13252 KB	Ok
40	Correct	5 ms	13252 KB	Ok
41	Correct	5 ms	13252 KB	Ok
42	Correct	5 ms	13252 KB	Ok
43	Correct	5 ms	13252 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Ok
2	Correct	1 ms	352 KB	Ok
3	Correct	1 ms	404 KB	Ok
4	Correct	1 ms	476 KB	Ok
5	Correct	1 ms	476 KB	Ok
6	Correct	1 ms	532 KB	Ok
7	Correct	2 ms	536 KB	Ok
8	Correct	1 ms	656 KB	Ok
9	Correct	1 ms	656 KB	Ok
10	Correct	1 ms	656 KB	Ok
11	Correct	1 ms	656 KB	Ok
12	Correct	1 ms	656 KB	Ok
13	Correct	1 ms	656 KB	Ok
14	Correct	2 ms	656 KB	Ok
15	Correct	2 ms	724 KB	Ok
16	Correct	2 ms	724 KB	Ok
17	Correct	1 ms	724 KB	Ok
18	Correct	3 ms	812 KB	Ok
19	Correct	10 ms	1216 KB	Ok
20	Correct	5 ms	1216 KB	Ok
21	Correct	11 ms	1416 KB	Ok
22	Correct	7 ms	1416 KB	Ok
23	Correct	1 ms	1416 KB	Ok
24	Correct	1 ms	1416 KB	Ok
25	Correct	1 ms	1416 KB	Ok
26	Correct	1 ms	1416 KB	Ok
27	Correct	1 ms	1416 KB	Ok
28	Correct	1 ms	1416 KB	Ok
29	Correct	1 ms	1416 KB	Ok
30	Correct	1 ms	1416 KB	Ok
31	Correct	1 ms	1416 KB	Ok
32	Correct	1 ms	1416 KB	Ok
33	Correct	1 ms	1416 KB	Ok
34	Correct	4 ms	13252 KB	Ok
35	Correct	5 ms	13252 KB	Ok
36	Correct	3 ms	13252 KB	Ok
37	Correct	3 ms	13252 KB	Ok
38	Correct	3 ms	13252 KB	Ok
39	Correct	5 ms	13252 KB	Ok
40	Correct	3 ms	13252 KB	Ok
41	Correct	3 ms	13252 KB	Ok
42	Correct	3 ms	13252 KB	Ok
43	Correct	5 ms	13252 KB	Ok
44	Correct	5 ms	13252 KB	Ok
45	Correct	5 ms	13252 KB	Ok
46	Correct	5 ms	13252 KB	Ok
47	Correct	5 ms	13252 KB	Ok
48	Correct	5 ms	13252 KB	Ok
49	Correct	5 ms	13252 KB	Ok
50	Correct	5 ms	13252 KB	Ok
51	Correct	5 ms	13252 KB	Ok
52	Correct	5 ms	13252 KB	Ok
53	Correct	5 ms	13252 KB	Ok
54	Correct	78 ms	13252 KB	Ok
55	Correct	74 ms	13252 KB	Ok
56	Correct	70 ms	13252 KB	Ok
57	Correct	59 ms	13252 KB	Ok
58	Correct	67 ms	13252 KB	Ok
59	Correct	63 ms	13252 KB	Ok
60	Correct	56 ms	13252 KB	Ok
61	Correct	56 ms	13252 KB	Ok
62	Correct	77 ms	13252 KB	Ok
63	Correct	60 ms	13252 KB	Ok
64	Correct	75 ms	13252 KB	Ok
65	Correct	74 ms	13252 KB	Ok
66	Correct	66 ms	13252 KB	Ok
67	Correct	55 ms	13252 KB	Ok
68	Correct	70 ms	13252 KB	Ok
69	Correct	168 ms	13252 KB	Ok
70	Correct	129 ms	13252 KB	Ok
71	Correct	130 ms	13252 KB	Ok
72	Correct	127 ms	13252 KB	Ok
73	Correct	126 ms	13252 KB	Ok
74	Correct	130 ms	13252 KB	Ok
75	Correct	142 ms	13252 KB	Ok
76	Correct	150 ms	13252 KB	Ok
77	Correct	127 ms	13252 KB	Ok
78	Correct	143 ms	13252 KB	Ok
79	Correct	143 ms	13252 KB	Ok
80	Correct	131 ms	13252 KB	Ok
81	Correct	128 ms	13252 KB	Ok
82	Correct	140 ms	13252 KB	Ok
83	Correct	128 ms	13252 KB	Ok

Subtask #7
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Ok
2	Correct	1 ms	352 KB	Ok
3	Correct	1 ms	404 KB	Ok
4	Correct	1 ms	476 KB	Ok
5	Correct	1 ms	476 KB	Ok
6	Correct	1 ms	532 KB	Ok
7	Correct	2 ms	536 KB	Ok
8	Correct	1 ms	656 KB	Ok
9	Correct	1 ms	656 KB	Ok
10	Correct	1 ms	656 KB	Ok
11	Correct	1 ms	656 KB	Ok
12	Correct	1 ms	656 KB	Ok
13	Correct	1 ms	656 KB	Ok
14	Correct	2 ms	656 KB	Ok
15	Correct	2 ms	724 KB	Ok
16	Correct	2 ms	724 KB	Ok
17	Correct	1 ms	724 KB	Ok
18	Correct	3 ms	812 KB	Ok
19	Correct	10 ms	1216 KB	Ok
20	Correct	5 ms	1216 KB	Ok
21	Correct	11 ms	1416 KB	Ok
22	Correct	7 ms	1416 KB	Ok
23	Correct	1 ms	1416 KB	Ok
24	Correct	1 ms	1416 KB	Ok
25	Correct	1 ms	1416 KB	Ok
26	Correct	1 ms	1416 KB	Ok
27	Correct	1 ms	1416 KB	Ok
28	Correct	1 ms	1416 KB	Ok
29	Correct	1 ms	1416 KB	Ok
30	Correct	1 ms	1416 KB	Ok
31	Correct	1 ms	1416 KB	Ok
32	Correct	1 ms	1416 KB	Ok
33	Correct	1 ms	1416 KB	Ok
34	Correct	1 ms	1416 KB	Ok
35	Correct	1 ms	1416 KB	Ok
36	Correct	1 ms	1416 KB	Ok
37	Correct	1 ms	1416 KB	Ok
38	Correct	1 ms	1416 KB	Ok
39	Correct	82 ms	10232 KB	Ok
40	Correct	74 ms	10232 KB	Ok
41	Correct	156 ms	12016 KB	Ok
42	Correct	113 ms	12016 KB	Ok
43	Correct	66 ms	12016 KB	Ok
44	Correct	124 ms	13252 KB	Ok
45	Correct	4 ms	13252 KB	Ok
46	Correct	5 ms	13252 KB	Ok
47	Correct	3 ms	13252 KB	Ok
48	Correct	3 ms	13252 KB	Ok
49	Correct	3 ms	13252 KB	Ok
50	Correct	5 ms	13252 KB	Ok
51	Correct	3 ms	13252 KB	Ok
52	Correct	3 ms	13252 KB	Ok
53	Correct	3 ms	13252 KB	Ok
54	Correct	5 ms	13252 KB	Ok
55	Correct	5 ms	13252 KB	Ok
56	Correct	5 ms	13252 KB	Ok
57	Correct	5 ms	13252 KB	Ok
58	Correct	5 ms	13252 KB	Ok
59	Correct	5 ms	13252 KB	Ok
60	Correct	5 ms	13252 KB	Ok
61	Correct	5 ms	13252 KB	Ok
62	Correct	5 ms	13252 KB	Ok
63	Correct	5 ms	13252 KB	Ok
64	Correct	5 ms	13252 KB	Ok
65	Correct	78 ms	13252 KB	Ok
66	Correct	74 ms	13252 KB	Ok
67	Correct	70 ms	13252 KB	Ok
68	Correct	59 ms	13252 KB	Ok
69	Correct	67 ms	13252 KB	Ok
70	Correct	63 ms	13252 KB	Ok
71	Correct	56 ms	13252 KB	Ok
72	Correct	56 ms	13252 KB	Ok
73	Correct	77 ms	13252 KB	Ok
74	Correct	60 ms	13252 KB	Ok
75	Correct	75 ms	13252 KB	Ok
76	Correct	74 ms	13252 KB	Ok
77	Correct	66 ms	13252 KB	Ok
78	Correct	55 ms	13252 KB	Ok
79	Correct	70 ms	13252 KB	Ok
80	Correct	168 ms	13252 KB	Ok
81	Correct	129 ms	13252 KB	Ok
82	Correct	130 ms	13252 KB	Ok
83	Correct	127 ms	13252 KB	Ok
84	Correct	126 ms	13252 KB	Ok
85	Correct	130 ms	13252 KB	Ok
86	Correct	142 ms	13252 KB	Ok
87	Correct	150 ms	13252 KB	Ok
88	Correct	127 ms	13252 KB	Ok
89	Correct	143 ms	13252 KB	Ok
90	Correct	143 ms	13252 KB	Ok
91	Correct	131 ms	13252 KB	Ok
92	Correct	128 ms	13252 KB	Ok
93	Correct	140 ms	13252 KB	Ok
94	Correct	128 ms	13252 KB	Ok
95	Correct	163 ms	13252 KB	Ok
96	Correct	242 ms	13252 KB	Ok
97	Correct	269 ms	13252 KB	Ok
98	Correct	177 ms	13252 KB	Ok
99	Correct	211 ms	13252 KB	Ok
100	Correct	224 ms	13252 KB	Ok
101	Correct	254 ms	13252 KB	Ok
102	Correct	200 ms	13252 KB	Ok
103	Correct	207 ms	13252 KB	Ok
104	Correct	258 ms	13252 KB	Ok
105	Correct	223 ms	13252 KB	Ok
106	Correct	202 ms	13252 KB	Ok
107	Correct	233 ms	13252 KB	Ok
108	Correct	278 ms	13252 KB	Ok
109	Correct	235 ms	13252 KB	Ok
110	Correct	614 ms	42112 KB	Ok
111	Correct	713 ms	43164 KB	Ok
112	Correct	639 ms	43164 KB	Ok
113	Correct	589 ms	43164 KB	Ok
114	Correct	665 ms	43164 KB	Ok
115	Correct	680 ms	43164 KB	Ok
116	Correct	676 ms	43164 KB	Ok
117	Correct	618 ms	43164 KB	Ok
118	Correct	595 ms	43164 KB	Ok
119	Correct	667 ms	43164 KB	Ok
120	Correct	629 ms	43236 KB	Ok
121	Correct	591 ms	43236 KB	Ok
122	Correct	606 ms	43236 KB	Ok
123	Correct	636 ms	43236 KB	Ok
124	Correct	621 ms	43236 KB	Ok
125	Correct	402 ms	43236 KB	Ok

답안 #42939

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