oj.uz

Submission #633585

# Submission time Handle Problem Language Result Execution time Memory
633585 2022-08-22T18:58:42 Z fabijan_cikac Nice sequence (IZhO18_sequence) C++17
100 / 100
 1796 ms 47728 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){
    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;
        }
    }
    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, 1))
                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 4 ms 6484 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6608 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 3 ms 6556 KB Ok
12 Correct 3 ms 6484 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6480 KB Ok
2 Correct 3 ms 6484 KB Ok
3 Correct 3 ms 6544 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 5 ms 6612 KB Ok
7 Correct 15 ms 7244 KB Ok
8 Correct 8 ms 6868 KB Ok
9 Correct 16 ms 7352 KB Ok
10 Correct 10 ms 6996 KB Ok

Subtask #3
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 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6484 KB Ok
8 Correct 4 ms 6484 KB Ok
9 Correct 3 ms 6604 KB Ok
10 Correct 3 ms 6604 KB Ok
11 Correct 4 ms 6600 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Ok
2 Correct 4 ms 6604 KB Ok
3 Correct 3 ms 6484 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6600 KB Ok
6 Correct 120 ms 14920 KB Ok
7 Correct 134 ms 14888 KB Ok
8 Correct 234 ms 17264 KB Ok
9 Correct 172 ms 17520 KB Ok
10 Correct 86 ms 12288 KB Ok
11 Correct 145 ms 17492 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 4 ms 6484 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6608 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 3 ms 6556 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 6484 KB Ok
17 Correct 3 ms 6484 KB Ok
18 Correct 3 ms 6484 KB Ok
19 Correct 3 ms 6484 KB Ok
20 Correct 4 ms 6484 KB Ok
21 Correct 3 ms 6604 KB Ok
22 Correct 3 ms 6604 KB Ok
23 Correct 4 ms 6600 KB Ok
24 Correct 4 ms 6612 KB Ok
25 Correct 5 ms 6624 KB Ok
26 Correct 5 ms 6612 KB Ok
27 Correct 4 ms 6612 KB Ok
28 Correct 4 ms 6608 KB Ok
29 Correct 4 ms 6612 KB Ok
30 Correct 4 ms 6600 KB Ok
31 Correct 5 ms 6612 KB Ok
32 Correct 5 ms 6668 KB Ok
33 Correct 5 ms 6604 KB Ok
34 Correct 11 ms 6792 KB Ok
35 Correct 8 ms 6868 KB Ok
36 Correct 10 ms 6812 KB Ok
37 Correct 9 ms 6868 KB Ok
38 Correct 8 ms 6868 KB Ok
39 Correct 7 ms 6740 KB Ok
40 Correct 8 ms 6868 KB Ok
41 Correct 8 ms 6860 KB Ok
42 Correct 8 ms 6784 KB Ok
43 Correct 8 ms 6860 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 4 ms 6484 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6608 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 3 ms 6556 KB Ok
12 Correct 3 ms 6484 KB Ok
13 Correct 4 ms 6480 KB Ok
14 Correct 3 ms 6484 KB Ok
15 Correct 3 ms 6544 KB Ok
16 Correct 4 ms 6484 KB Ok
17 Correct 3 ms 6484 KB Ok
18 Correct 5 ms 6612 KB Ok
19 Correct 15 ms 7244 KB Ok
20 Correct 8 ms 6868 KB Ok
21 Correct 16 ms 7352 KB Ok
22 Correct 10 ms 6996 KB Ok
23 Correct 3 ms 6484 KB Ok
24 Correct 3 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 6484 KB Ok
30 Correct 4 ms 6484 KB Ok
31 Correct 3 ms 6604 KB Ok
32 Correct 3 ms 6604 KB Ok
33 Correct 4 ms 6600 KB Ok
34 Correct 4 ms 6612 KB Ok
35 Correct 5 ms 6624 KB Ok
36 Correct 5 ms 6612 KB Ok
37 Correct 4 ms 6612 KB Ok
38 Correct 4 ms 6608 KB Ok
39 Correct 4 ms 6612 KB Ok
40 Correct 4 ms 6600 KB Ok
41 Correct 5 ms 6612 KB Ok
42 Correct 5 ms 6668 KB Ok
43 Correct 5 ms 6604 KB Ok
44 Correct 11 ms 6792 KB Ok
45 Correct 8 ms 6868 KB Ok
46 Correct 10 ms 6812 KB Ok
47 Correct 9 ms 6868 KB Ok
48 Correct 8 ms 6868 KB Ok
49 Correct 7 ms 6740 KB Ok
50 Correct 8 ms 6868 KB Ok
51 Correct 8 ms 6860 KB Ok
52 Correct 8 ms 6784 KB Ok
53 Correct 8 ms 6860 KB Ok
54 Correct 91 ms 9420 KB Ok
55 Correct 123 ms 9916 KB Ok
56 Correct 108 ms 9688 KB Ok
57 Correct 79 ms 9020 KB Ok
58 Correct 87 ms 9676 KB Ok
59 Correct 81 ms 9552 KB Ok
60 Correct 73 ms 9260 KB Ok
61 Correct 73 ms 9172 KB Ok
62 Correct 99 ms 10012 KB Ok
63 Correct 89 ms 9348 KB Ok
64 Correct 132 ms 9852 KB Ok
65 Correct 85 ms 9668 KB Ok
66 Correct 81 ms 9344 KB Ok
67 Correct 86 ms 9168 KB Ok
68 Correct 103 ms 9500 KB Ok
69 Correct 191 ms 15784 KB Ok
70 Correct 227 ms 16276 KB Ok
71 Correct 181 ms 15820 KB Ok
72 Correct 202 ms 15692 KB Ok
73 Correct 185 ms 16072 KB Ok
74 Correct 186 ms 15656 KB Ok
75 Correct 205 ms 15672 KB Ok
76 Correct 199 ms 15948 KB Ok
77 Correct 183 ms 15664 KB Ok
78 Correct 205 ms 15692 KB Ok
79 Correct 200 ms 16076 KB Ok
80 Correct 186 ms 15756 KB Ok
81 Correct 225 ms 16076 KB Ok
82 Correct 183 ms 15920 KB Ok
83 Correct 183 ms 15908 KB Ok

Subtask #7
24.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 4 ms 6484 KB Ok
4 Correct 4 ms 6484 KB Ok
5 Correct 3 ms 6484 KB Ok
6 Correct 3 ms 6484 KB Ok
7 Correct 3 ms 6608 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 3 ms 6556 KB Ok
12 Correct 3 ms 6484 KB Ok
13 Correct 4 ms 6480 KB Ok
14 Correct 3 ms 6484 KB Ok
15 Correct 3 ms 6544 KB Ok
16 Correct 4 ms 6484 KB Ok
17 Correct 3 ms 6484 KB Ok
18 Correct 5 ms 6612 KB Ok
19 Correct 15 ms 7244 KB Ok
20 Correct 8 ms 6868 KB Ok
21 Correct 16 ms 7352 KB Ok
22 Correct 10 ms 6996 KB Ok
23 Correct 3 ms 6484 KB Ok
24 Correct 3 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 6484 KB Ok
30 Correct 4 ms 6484 KB Ok
31 Correct 3 ms 6604 KB Ok
32 Correct 3 ms 6604 KB Ok
33 Correct 4 ms 6600 KB Ok
34 Correct 4 ms 6484 KB Ok
35 Correct 4 ms 6604 KB Ok
36 Correct 3 ms 6484 KB Ok
37 Correct 4 ms 6484 KB Ok
38 Correct 3 ms 6600 KB Ok
39 Correct 120 ms 14920 KB Ok
40 Correct 134 ms 14888 KB Ok
41 Correct 234 ms 17264 KB Ok
42 Correct 172 ms 17520 KB Ok
43 Correct 86 ms 12288 KB Ok
44 Correct 145 ms 17492 KB Ok
45 Correct 4 ms 6612 KB Ok
46 Correct 5 ms 6624 KB Ok
47 Correct 5 ms 6612 KB Ok
48 Correct 4 ms 6612 KB Ok
49 Correct 4 ms 6608 KB Ok
50 Correct 4 ms 6612 KB Ok
51 Correct 4 ms 6600 KB Ok
52 Correct 5 ms 6612 KB Ok
53 Correct 5 ms 6668 KB Ok
54 Correct 5 ms 6604 KB Ok
55 Correct 11 ms 6792 KB Ok
56 Correct 8 ms 6868 KB Ok
57 Correct 10 ms 6812 KB Ok
58 Correct 9 ms 6868 KB Ok
59 Correct 8 ms 6868 KB Ok
60 Correct 7 ms 6740 KB Ok
61 Correct 8 ms 6868 KB Ok
62 Correct 8 ms 6860 KB Ok
63 Correct 8 ms 6784 KB Ok
64 Correct 8 ms 6860 KB Ok
65 Correct 91 ms 9420 KB Ok
66 Correct 123 ms 9916 KB Ok
67 Correct 108 ms 9688 KB Ok
68 Correct 79 ms 9020 KB Ok
69 Correct 87 ms 9676 KB Ok
70 Correct 81 ms 9552 KB Ok
71 Correct 73 ms 9260 KB Ok
72 Correct 73 ms 9172 KB Ok
73 Correct 99 ms 10012 KB Ok
74 Correct 89 ms 9348 KB Ok
75 Correct 132 ms 9852 KB Ok
76 Correct 85 ms 9668 KB Ok
77 Correct 81 ms 9344 KB Ok
78 Correct 86 ms 9168 KB Ok
79 Correct 103 ms 9500 KB Ok
80 Correct 191 ms 15784 KB Ok
81 Correct 227 ms 16276 KB Ok
82 Correct 181 ms 15820 KB Ok
83 Correct 202 ms 15692 KB Ok
84 Correct 185 ms 16072 KB Ok
85 Correct 186 ms 15656 KB Ok
86 Correct 205 ms 15672 KB Ok
87 Correct 199 ms 15948 KB Ok
88 Correct 183 ms 15664 KB Ok
89 Correct 205 ms 15692 KB Ok
90 Correct 200 ms 16076 KB Ok
91 Correct 186 ms 15756 KB Ok
92 Correct 225 ms 16076 KB Ok
93 Correct 183 ms 15920 KB Ok
94 Correct 183 ms 15908 KB Ok
95 Correct 228 ms 14088 KB Ok
96 Correct 321 ms 17756 KB Ok
97 Correct 297 ms 16596 KB Ok
98 Correct 209 ms 14924 KB Ok
99 Correct 297 ms 15564 KB Ok
100 Correct 314 ms 16384 KB Ok
101 Correct 296 ms 16200 KB Ok
102 Correct 290 ms 16076 KB Ok
103 Correct 284 ms 16564 KB Ok
104 Correct 367 ms 17516 KB Ok
105 Correct 317 ms 17604 KB Ok
106 Correct 266 ms 16008 KB Ok
107 Correct 304 ms 16844 KB Ok
108 Correct 358 ms 18008 KB Ok
109 Correct 320 ms 17080 KB Ok
110 Correct 1540 ms 45088 KB Ok
111 Correct 1749 ms 46872 KB Ok
112 Correct 1574 ms 47240 KB Ok
113 Correct 1718 ms 45804 KB Ok
114 Correct 1457 ms 47652 KB Ok
115 Correct 1671 ms 46936 KB Ok
116 Correct 1675 ms 47616 KB Ok
117 Correct 1652 ms 46004 KB Ok
118 Correct 1556 ms 47580 KB Ok
119 Correct 1660 ms 45708 KB Ok
120 Correct 1560 ms 46432 KB Ok
121 Correct 1446 ms 45904 KB Ok
122 Correct 1713 ms 46644 KB Ok
123 Correct 1796 ms 46828 KB Ok
124 Correct 1622 ms 47728 KB Ok
125 Correct 895 ms 29108 KB Ok