oj.uz

Submission #42940

# Submission time Handle Problem Language Result Execution time Memory
42940 2018-03-06T11:31:35 Z bash Nice sequence (IZhO18_sequence) C++14
43 / 100
 2000 ms 10252 KB 
/**
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)
    	dfs(v - N);
    if (v + M <= sz )
    	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Ok
2 Correct 1 ms 352 KB Ok
3 Correct 1 ms 424 KB Ok
4 Correct 2 ms 496 KB Ok
5 Correct 2 ms 644 KB Ok
6 Correct 2 ms 644 KB Ok
7 Correct 1 ms 644 KB Ok
8 Correct 1 ms 644 KB Ok
9 Correct 1 ms 644 KB Ok
10 Correct 1 ms 644 KB Ok
11 Correct 2 ms 644 KB Ok
12 Correct 1 ms 644 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 644 KB Ok
2 Correct 1 ms 644 KB Ok
3 Correct 1 ms 644 KB Ok
4 Correct 2 ms 644 KB Ok
5 Correct 2 ms 644 KB Ok
6 Correct 38 ms 736 KB Ok
7 Correct 1209 ms 1540 KB Ok
8 Correct 297 ms 1540 KB Ok
9 Correct 987 ms 1592 KB Ok
10 Correct 579 ms 1592 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1592 KB Ok
2 Correct 1 ms 1592 KB Ok
3 Correct 1 ms 1592 KB Ok
4 Correct 1 ms 1592 KB Ok
5 Correct 1 ms 1592 KB Ok
6 Correct 1 ms 1592 KB Ok
7 Correct 1 ms 1592 KB Ok
8 Correct 1 ms 1592 KB Ok
9 Correct 2 ms 1592 KB Ok
10 Correct 1 ms 1592 KB Ok
11 Correct 1 ms 1592 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1592 KB Ok
2 Correct 1 ms 1592 KB Ok
3 Correct 1 ms 1592 KB Ok
4 Correct 1 ms 1592 KB Ok
5 Correct 2 ms 1592 KB Ok
6 Execution timed out 2023 ms 5572 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Ok
2 Correct 1 ms 352 KB Ok
3 Correct 1 ms 424 KB Ok
4 Correct 2 ms 496 KB Ok
5 Correct 2 ms 644 KB Ok
6 Correct 2 ms 644 KB Ok
7 Correct 1 ms 644 KB Ok
8 Correct 1 ms 644 KB Ok
9 Correct 1 ms 644 KB Ok
10 Correct 1 ms 644 KB Ok
11 Correct 2 ms 644 KB Ok
12 Correct 1 ms 644 KB Ok
13 Correct 1 ms 1592 KB Ok
14 Correct 1 ms 1592 KB Ok
15 Correct 1 ms 1592 KB Ok
16 Correct 1 ms 1592 KB Ok
17 Correct 1 ms 1592 KB Ok
18 Correct 1 ms 1592 KB Ok
19 Correct 1 ms 1592 KB Ok
20 Correct 1 ms 1592 KB Ok
21 Correct 2 ms 1592 KB Ok
22 Correct 1 ms 1592 KB Ok
23 Correct 1 ms 1592 KB Ok
24 Correct 3 ms 5572 KB Ok
25 Correct 3 ms 5572 KB Ok
26 Correct 3 ms 5572 KB Ok
27 Correct 3 ms 5572 KB Ok
28 Correct 3 ms 5572 KB Ok
29 Correct 3 ms 5572 KB Ok
30 Correct 4 ms 5572 KB Ok
31 Correct 3 ms 5572 KB Ok
32 Correct 3 ms 5572 KB Ok
33 Correct 3 ms 5572 KB Ok
34 Correct 8 ms 5572 KB Ok
35 Correct 8 ms 5572 KB Ok
36 Correct 16 ms 5572 KB Ok
37 Correct 9 ms 5572 KB Ok
38 Correct 8 ms 5572 KB Ok
39 Correct 7 ms 5572 KB Ok
40 Correct 11 ms 5572 KB Ok
41 Correct 8 ms 5572 KB Ok
42 Correct 11 ms 5572 KB Ok
43 Correct 9 ms 5572 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Ok
2 Correct 1 ms 352 KB Ok
3 Correct 1 ms 424 KB Ok
4 Correct 2 ms 496 KB Ok
5 Correct 2 ms 644 KB Ok
6 Correct 2 ms 644 KB Ok
7 Correct 1 ms 644 KB Ok
8 Correct 1 ms 644 KB Ok
9 Correct 1 ms 644 KB Ok
10 Correct 1 ms 644 KB Ok
11 Correct 2 ms 644 KB Ok
12 Correct 1 ms 644 KB Ok
13 Correct 1 ms 644 KB Ok
14 Correct 1 ms 644 KB Ok
15 Correct 1 ms 644 KB Ok
16 Correct 2 ms 644 KB Ok
17 Correct 2 ms 644 KB Ok
18 Correct 38 ms 736 KB Ok
19 Correct 1209 ms 1540 KB Ok
20 Correct 297 ms 1540 KB Ok
21 Correct 987 ms 1592 KB Ok
22 Correct 579 ms 1592 KB Ok
23 Correct 1 ms 1592 KB Ok
24 Correct 1 ms 1592 KB Ok
25 Correct 1 ms 1592 KB Ok
26 Correct 1 ms 1592 KB Ok
27 Correct 1 ms 1592 KB Ok
28 Correct 1 ms 1592 KB Ok
29 Correct 1 ms 1592 KB Ok
30 Correct 1 ms 1592 KB Ok
31 Correct 2 ms 1592 KB Ok
32 Correct 1 ms 1592 KB Ok
33 Correct 1 ms 1592 KB Ok
34 Correct 3 ms 5572 KB Ok
35 Correct 3 ms 5572 KB Ok
36 Correct 3 ms 5572 KB Ok
37 Correct 3 ms 5572 KB Ok
38 Correct 3 ms 5572 KB Ok
39 Correct 3 ms 5572 KB Ok
40 Correct 4 ms 5572 KB Ok
41 Correct 3 ms 5572 KB Ok
42 Correct 3 ms 5572 KB Ok
43 Correct 3 ms 5572 KB Ok
44 Correct 8 ms 5572 KB Ok
45 Correct 8 ms 5572 KB Ok
46 Correct 16 ms 5572 KB Ok
47 Correct 9 ms 5572 KB Ok
48 Correct 8 ms 5572 KB Ok
49 Correct 7 ms 5572 KB Ok
50 Correct 11 ms 5572 KB Ok
51 Correct 8 ms 5572 KB Ok
52 Correct 11 ms 5572 KB Ok
53 Correct 9 ms 5572 KB Ok
54 Correct 87 ms 5572 KB Ok
55 Correct 116 ms 5572 KB Ok
56 Correct 95 ms 5572 KB Ok
57 Correct 69 ms 5572 KB Ok
58 Correct 80 ms 5572 KB Ok
59 Correct 77 ms 5572 KB Ok
60 Correct 65 ms 5572 KB Ok
61 Correct 69 ms 5572 KB Ok
62 Correct 99 ms 5572 KB Ok
63 Correct 71 ms 5572 KB Ok
64 Correct 86 ms 5572 KB Ok
65 Correct 88 ms 5572 KB Ok
66 Correct 75 ms 5572 KB Ok
67 Correct 67 ms 5572 KB Ok
68 Correct 100 ms 5572 KB Ok
69 Execution timed out 2028 ms 10252 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Ok
2 Correct 1 ms 352 KB Ok
3 Correct 1 ms 424 KB Ok
4 Correct 2 ms 496 KB Ok
5 Correct 2 ms 644 KB Ok
6 Correct 2 ms 644 KB Ok
7 Correct 1 ms 644 KB Ok
8 Correct 1 ms 644 KB Ok
9 Correct 1 ms 644 KB Ok
10 Correct 1 ms 644 KB Ok
11 Correct 2 ms 644 KB Ok
12 Correct 1 ms 644 KB Ok
13 Correct 1 ms 644 KB Ok
14 Correct 1 ms 644 KB Ok
15 Correct 1 ms 644 KB Ok
16 Correct 2 ms 644 KB Ok
17 Correct 2 ms 644 KB Ok
18 Correct 38 ms 736 KB Ok
19 Correct 1209 ms 1540 KB Ok
20 Correct 297 ms 1540 KB Ok
21 Correct 987 ms 1592 KB Ok
22 Correct 579 ms 1592 KB Ok
23 Correct 1 ms 1592 KB Ok
24 Correct 1 ms 1592 KB Ok
25 Correct 1 ms 1592 KB Ok
26 Correct 1 ms 1592 KB Ok
27 Correct 1 ms 1592 KB Ok
28 Correct 1 ms 1592 KB Ok
29 Correct 1 ms 1592 KB Ok
30 Correct 1 ms 1592 KB Ok
31 Correct 2 ms 1592 KB Ok
32 Correct 1 ms 1592 KB Ok
33 Correct 1 ms 1592 KB Ok
34 Correct 1 ms 1592 KB Ok
35 Correct 1 ms 1592 KB Ok
36 Correct 1 ms 1592 KB Ok
37 Correct 1 ms 1592 KB Ok
38 Correct 2 ms 1592 KB Ok
39 Execution timed out 2023 ms 5572 KB Time limit exceeded
40 Halted 0 ms 0 KB -