oj.uz

Submission #633583

# Submission time Handle Problem Language Result Execution time Memory
633583 2022-08-22T18:50:25 Z fabijan_cikac Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 50880 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

using namespace std;

#define ll long long int
#define pb push_back

const int N = 400100;
const ll INF = 1e18;

int t, n, m; int a[N];
int v[N][2];
int u[N][2]; int tme;

void rec(int x){
    if (u[x][0] != -1 && a[x] == 0) rec(u[x][0]);
    if (u[x][1] != -1 && a[x] == 0) rec(u[x][1]);
    a[x] = --tme;
}

int bio[N]; ll sz = 0;

bool dfs(int x){
	if(bio[x]) return bio[x] == 1;
	bio[x] = 1;
	if(v[x][0] != -1 && dfs(v[x][0])) return 1;
	if(v[x][1] != -1 && dfs(v[x][1])) return 1;
	bio[x] = 2;
	return 0;
}

void clear_it(int k){
    for (int i = 0; i <= k; ++i){
        bio[i] = 0;
        v[i][0] = -1; u[i][0] = -1;
        v[i][1] = -1; u[i][1] = -1;
    }
}

bool good_seq(int k, int samo = 1){
    clear_it(k);
    for (int i = n; i <= k; ++i){
        v[i - n][0] = i; u[i][0] = (i - n);
    }
    for (int i = m; i <= k; ++i){
        v[i][1] = (i - m); u[i - m][1] = i;
    }
    for (int i = 0; i <= k; ++i) a[i] = 0;
    for (int i = 0; i <= k; ++i){
        if (!bio[i]){
            if (dfs(i)) return 0;
        }
    }
    for (int i = 0; i <= k; ++i){
        if (!bio[i]) return 0;
    }
    if(samo) return 1;
    for (int i = 0; i <= k; ++i){
        if (a[i] == 0) rec(i);
    }
    for (int i = 1; i <= k; ++i) a[i] -= a[0];
    a[0] = 0; return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> t; memset(v, -1, sizeof(v));
    memset(u, -1, sizeof(u));
    while (t--){
        if (t < 0) break;
        cin >> n >> m;
        int l = 0; int r = n + m + 1;
        while (l < r){
            //printf("%d %d\n", l, r);
            int mid = (l + r + 1) / 2;
            if (good_seq(mid))
                l = mid;
            else r = mid - 1;
        }
        good_seq(l, 0);
        cout << l << '\n';
        for (int i = 1; i <= l; ++i)
            cout << a[i] - a[i - 1] << ' ';
        cout << '\n';
    }

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6600 KB Ok
5 Correct 3 ms 6612 KB Ok
6 Correct 6 ms 6712 KB Ok
7 Correct 18 ms 7252 KB Ok
8 Correct 10 ms 6896 KB Ok
9 Correct 24 ms 7392 KB Ok
10 Correct 13 ms 6996 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6608 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6604 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 192 ms 16056 KB Ok
7 Correct 184 ms 16516 KB Ok
8 Correct 365 ms 18692 KB Ok
9 Correct 265 ms 18816 KB Ok
10 Correct 131 ms 13016 KB Ok
11 Correct 214 ms 19196 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6608 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6484 KB Ok
9 Correct 3 ms 6608 KB Ok
10 Correct 3 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6484 KB Ok
13 Correct 3 ms 6496 KB Ok
14 Correct 4 ms 6484 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6484 KB Ok
17 Correct 3 ms 6484 KB Ok
18 Correct 3 ms 6484 KB Ok
19 Correct 3 ms 6612 KB Ok
20 Correct 3 ms 6608 KB Ok
21 Correct 3 ms 6484 KB Ok
22 Correct 3 ms 6484 KB Ok
23 Correct 3 ms 6612 KB Ok
24 Correct 6 ms 6612 KB Ok
25 Correct 5 ms 6612 KB Ok
26 Correct 5 ms 6612 KB Ok
27 Correct 5 ms 6620 KB Ok
28 Correct 5 ms 6628 KB Ok
29 Correct 5 ms 6628 KB Ok
30 Correct 4 ms 6628 KB Ok
31 Correct 6 ms 6628 KB Ok
32 Correct 6 ms 6628 KB Ok
33 Correct 7 ms 6612 KB Ok
34 Correct 10 ms 6856 KB Ok
35 Correct 9 ms 6856 KB Ok
36 Correct 10 ms 6852 KB Ok
37 Correct 10 ms 6868 KB Ok
38 Correct 9 ms 6868 KB Ok
39 Correct 9 ms 6820 KB Ok
40 Correct 10 ms 6868 KB Ok
41 Correct 9 ms 6868 KB Ok
42 Correct 9 ms 6876 KB Ok
43 Correct 14 ms 6820 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6608 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6484 KB Ok
9 Correct 3 ms 6608 KB Ok
10 Correct 3 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6484 KB Ok
13 Correct 3 ms 6484 KB Ok
14 Correct 3 ms 6484 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6600 KB Ok
17 Correct 3 ms 6612 KB Ok
18 Correct 6 ms 6712 KB Ok
19 Correct 18 ms 7252 KB Ok
20 Correct 10 ms 6896 KB Ok
21 Correct 24 ms 7392 KB Ok
22 Correct 13 ms 6996 KB Ok
23 Correct 3 ms 6496 KB Ok
24 Correct 4 ms 6484 KB Ok
25 Correct 3 ms 6484 KB Ok
26 Correct 3 ms 6484 KB Ok
27 Correct 3 ms 6484 KB Ok
28 Correct 3 ms 6484 KB Ok
29 Correct 3 ms 6612 KB Ok
30 Correct 3 ms 6608 KB Ok
31 Correct 3 ms 6484 KB Ok
32 Correct 3 ms 6484 KB Ok
33 Correct 3 ms 6612 KB Ok
34 Correct 6 ms 6612 KB Ok
35 Correct 5 ms 6612 KB Ok
36 Correct 5 ms 6612 KB Ok
37 Correct 5 ms 6620 KB Ok
38 Correct 5 ms 6628 KB Ok
39 Correct 5 ms 6628 KB Ok
40 Correct 4 ms 6628 KB Ok
41 Correct 6 ms 6628 KB Ok
42 Correct 6 ms 6628 KB Ok
43 Correct 7 ms 6612 KB Ok
44 Correct 10 ms 6856 KB Ok
45 Correct 9 ms 6856 KB Ok
46 Correct 10 ms 6852 KB Ok
47 Correct 10 ms 6868 KB Ok
48 Correct 9 ms 6868 KB Ok
49 Correct 9 ms 6820 KB Ok
50 Correct 10 ms 6868 KB Ok
51 Correct 9 ms 6868 KB Ok
52 Correct 9 ms 6876 KB Ok
53 Correct 14 ms 6820 KB Ok
54 Correct 118 ms 9428 KB Ok
55 Correct 132 ms 10060 KB Ok
56 Correct 140 ms 9700 KB Ok
57 Correct 106 ms 9088 KB Ok
58 Correct 115 ms 9644 KB Ok
59 Correct 108 ms 9656 KB Ok
60 Correct 94 ms 9160 KB Ok
61 Correct 94 ms 9180 KB Ok
62 Correct 129 ms 10000 KB Ok
63 Correct 103 ms 9336 KB Ok
64 Correct 138 ms 9844 KB Ok
65 Correct 119 ms 9696 KB Ok
66 Correct 109 ms 9452 KB Ok
67 Correct 108 ms 9272 KB Ok
68 Correct 109 ms 9616 KB Ok
69 Correct 335 ms 16584 KB Ok
70 Correct 354 ms 17036 KB Ok
71 Correct 353 ms 16712 KB Ok
72 Correct 357 ms 16408 KB Ok
73 Correct 316 ms 16852 KB Ok
74 Correct 334 ms 16588 KB Ok
75 Correct 364 ms 16588 KB Ok
76 Correct 371 ms 16640 KB Ok
77 Correct 323 ms 16560 KB Ok
78 Correct 367 ms 16504 KB Ok
79 Correct 363 ms 16884 KB Ok
80 Correct 336 ms 16588 KB Ok
81 Correct 361 ms 16856 KB Ok
82 Correct 315 ms 16644 KB Ok
83 Correct 316 ms 16680 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 3 ms 6484 KB Ok
5 Correct 3 ms 6608 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 3 ms 6484 KB Ok
9 Correct 3 ms 6608 KB Ok
10 Correct 3 ms 6484 KB Ok
11 Correct 4 ms 6484 KB Ok
12 Correct 3 ms 6484 KB Ok
13 Correct 3 ms 6484 KB Ok
14 Correct 3 ms 6484 KB Ok
15 Correct 3 ms 6484 KB Ok
16 Correct 3 ms 6600 KB Ok
17 Correct 3 ms 6612 KB Ok
18 Correct 6 ms 6712 KB Ok
19 Correct 18 ms 7252 KB Ok
20 Correct 10 ms 6896 KB Ok
21 Correct 24 ms 7392 KB Ok
22 Correct 13 ms 6996 KB Ok
23 Correct 3 ms 6496 KB Ok
24 Correct 4 ms 6484 KB Ok
25 Correct 3 ms 6484 KB Ok
26 Correct 3 ms 6484 KB Ok
27 Correct 3 ms 6484 KB Ok
28 Correct 3 ms 6484 KB Ok
29 Correct 3 ms 6612 KB Ok
30 Correct 3 ms 6608 KB Ok
31 Correct 3 ms 6484 KB Ok
32 Correct 3 ms 6484 KB Ok
33 Correct 3 ms 6612 KB Ok
34 Correct 3 ms 6484 KB Ok
35 Correct 3 ms 6608 KB Ok
36 Correct 3 ms 6484 KB Ok
37 Correct 3 ms 6604 KB Ok
38 Correct 3 ms 6484 KB Ok
39 Correct 192 ms 16056 KB Ok
40 Correct 184 ms 16516 KB Ok
41 Correct 365 ms 18692 KB Ok
42 Correct 265 ms 18816 KB Ok
43 Correct 131 ms 13016 KB Ok
44 Correct 214 ms 19196 KB Ok
45 Correct 6 ms 6612 KB Ok
46 Correct 5 ms 6612 KB Ok
47 Correct 5 ms 6612 KB Ok
48 Correct 5 ms 6620 KB Ok
49 Correct 5 ms 6628 KB Ok
50 Correct 5 ms 6628 KB Ok
51 Correct 4 ms 6628 KB Ok
52 Correct 6 ms 6628 KB Ok
53 Correct 6 ms 6628 KB Ok
54 Correct 7 ms 6612 KB Ok
55 Correct 10 ms 6856 KB Ok
56 Correct 9 ms 6856 KB Ok
57 Correct 10 ms 6852 KB Ok
58 Correct 10 ms 6868 KB Ok
59 Correct 9 ms 6868 KB Ok
60 Correct 9 ms 6820 KB Ok
61 Correct 10 ms 6868 KB Ok
62 Correct 9 ms 6868 KB Ok
63 Correct 9 ms 6876 KB Ok
64 Correct 14 ms 6820 KB Ok
65 Correct 118 ms 9428 KB Ok
66 Correct 132 ms 10060 KB Ok
67 Correct 140 ms 9700 KB Ok
68 Correct 106 ms 9088 KB Ok
69 Correct 115 ms 9644 KB Ok
70 Correct 108 ms 9656 KB Ok
71 Correct 94 ms 9160 KB Ok
72 Correct 94 ms 9180 KB Ok
73 Correct 129 ms 10000 KB Ok
74 Correct 103 ms 9336 KB Ok
75 Correct 138 ms 9844 KB Ok
76 Correct 119 ms 9696 KB Ok
77 Correct 109 ms 9452 KB Ok
78 Correct 108 ms 9272 KB Ok
79 Correct 109 ms 9616 KB Ok
80 Correct 335 ms 16584 KB Ok
81 Correct 354 ms 17036 KB Ok
82 Correct 353 ms 16712 KB Ok
83 Correct 357 ms 16408 KB Ok
84 Correct 316 ms 16852 KB Ok
85 Correct 334 ms 16588 KB Ok
86 Correct 364 ms 16588 KB Ok
87 Correct 371 ms 16640 KB Ok
88 Correct 323 ms 16560 KB Ok
89 Correct 367 ms 16504 KB Ok
90 Correct 363 ms 16884 KB Ok
91 Correct 336 ms 16588 KB Ok
92 Correct 361 ms 16856 KB Ok
93 Correct 315 ms 16644 KB Ok
94 Correct 316 ms 16680 KB Ok
95 Correct 318 ms 14172 KB Ok
96 Correct 443 ms 17960 KB Ok
97 Correct 396 ms 16716 KB Ok
98 Correct 297 ms 14956 KB Ok
99 Correct 361 ms 15500 KB Ok
100 Correct 381 ms 16332 KB Ok
101 Correct 394 ms 16176 KB Ok
102 Correct 392 ms 16176 KB Ok
103 Correct 380 ms 16464 KB Ok
104 Correct 474 ms 17528 KB Ok
105 Correct 437 ms 17604 KB Ok
106 Correct 364 ms 16036 KB Ok
107 Correct 424 ms 16836 KB Ok
108 Correct 460 ms 17984 KB Ok
109 Correct 423 ms 17052 KB Ok
110 Correct 1800 ms 48276 KB Ok
111 Correct 1991 ms 49880 KB Ok
112 Correct 1958 ms 50284 KB Ok
113 Correct 1967 ms 49044 KB Ok
114 Correct 1936 ms 50880 KB Ok
115 Execution timed out 2007 ms 50100 KB Time limit exceeded
116 Halted 0 ms 0 KB -