oj.uz

Submission #682609

# Submission time Handle Problem Language Result Execution time Memory
682609 2023-01-16T15:08:07 Z FedShat Nice sequence (IZhO18_sequence) C++17
100 / 100
 1119 ms 61292 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

constexpr int N = 4e5 + 1;
int used[N];
bool cycle = 0;
int n, m;

void dfs1(int v, int sz) {
    used[v] = 0;
    for (auto u : {v - m, v + n}) {
        if (u < 0 || u >= sz) {
            continue;
        }
        if (used[u] == -1) {
            dfs1(u, sz);
        } else if (used[u] == 0) {
            cycle = 1;
        }
    }
    used[v] = 1;
}

vector<ll> dp;

void dfs2(int v, int sz) {
    for (auto u : {v - m, v + n}) {
        if (u < 0 || u >= sz) {
            continue;
        }
        if (dp[u] == 0) {
            dfs2(u, sz);
        }
        dp[v] = max(dp[v], dp[u] + 1);
    }
    dp[v] = max(dp[v], v + 1ll);
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        int l = 0, r = n + m;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            cycle = 0;
            memset(used, -1, sizeof(int) * (mid + 1));
            for (int i = 0; i <= mid; ++i) {
                if (used[i] == -1) {
                    dfs1(i, mid + 1);
                }
            }
            if (!cycle) {
                l = mid;
            } else {
                r = mid;
            }
        }
        memset(used, -1, sizeof(int) * (l + 1));
        dp.assign(l + 1, 0);
        for (int i = 0; i <= l; ++i) {
            if (dp[i] == 0) {
                dfs2(i, l + 1);
            }
        }
        for (int i = 0; i + m <= l; ++i) {
            assert(dp[i + m] > dp[i]);
        }
        for (int i = 0; i + n <= l; ++i) {
            assert(dp[i + n] < dp[i]);
        }
        cout << l << "\n";
        for (int i = 1; i <= l; ++i) {
            assert(dp[i] != dp[i - 1]);
            cout << dp[i] - dp[i - 1] << " ";
        }
        cout << "\n";
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 3 ms 468 KB Ok
7 Correct 15 ms 1396 KB Ok
8 Correct 7 ms 828 KB Ok
9 Correct 17 ms 1580 KB Ok
10 Correct 10 ms 980 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 169 ms 14284 KB Ok
7 Correct 160 ms 20060 KB Ok
8 Correct 310 ms 21508 KB Ok
9 Correct 230 ms 20048 KB Ok
10 Correct 114 ms 9324 KB Ok
11 Correct 193 ms 18428 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 300 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 0 ms 212 KB Ok
19 Correct 0 ms 212 KB Ok
20 Correct 0 ms 212 KB Ok
21 Correct 0 ms 212 KB Ok
22 Correct 0 ms 212 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 3 ms 340 KB Ok
25 Correct 3 ms 468 KB Ok
26 Correct 3 ms 340 KB Ok
27 Correct 2 ms 340 KB Ok
28 Correct 2 ms 336 KB Ok
29 Correct 2 ms 340 KB Ok
30 Correct 2 ms 340 KB Ok
31 Correct 3 ms 340 KB Ok
32 Correct 3 ms 340 KB Ok
33 Correct 2 ms 340 KB Ok
34 Correct 6 ms 596 KB Ok
35 Correct 6 ms 724 KB Ok
36 Correct 6 ms 728 KB Ok
37 Correct 6 ms 724 KB Ok
38 Correct 6 ms 724 KB Ok
39 Correct 5 ms 724 KB Ok
40 Correct 6 ms 712 KB Ok
41 Correct 6 ms 724 KB Ok
42 Correct 6 ms 596 KB Ok
43 Correct 6 ms 724 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 300 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 3 ms 468 KB Ok
19 Correct 15 ms 1396 KB Ok
20 Correct 7 ms 828 KB Ok
21 Correct 17 ms 1580 KB Ok
22 Correct 10 ms 980 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 0 ms 212 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 3 ms 340 KB Ok
35 Correct 3 ms 468 KB Ok
36 Correct 3 ms 340 KB Ok
37 Correct 2 ms 340 KB Ok
38 Correct 2 ms 336 KB Ok
39 Correct 2 ms 340 KB Ok
40 Correct 2 ms 340 KB Ok
41 Correct 3 ms 340 KB Ok
42 Correct 3 ms 340 KB Ok
43 Correct 2 ms 340 KB Ok
44 Correct 6 ms 596 KB Ok
45 Correct 6 ms 724 KB Ok
46 Correct 6 ms 728 KB Ok
47 Correct 6 ms 724 KB Ok
48 Correct 6 ms 724 KB Ok
49 Correct 5 ms 724 KB Ok
50 Correct 6 ms 712 KB Ok
51 Correct 6 ms 724 KB Ok
52 Correct 6 ms 596 KB Ok
53 Correct 6 ms 724 KB Ok
54 Correct 117 ms 2700 KB Ok
55 Correct 141 ms 2916 KB Ok
56 Correct 139 ms 3168 KB Ok
57 Correct 98 ms 2452 KB Ok
58 Correct 126 ms 2748 KB Ok
59 Correct 111 ms 2584 KB Ok
60 Correct 99 ms 2524 KB Ok
61 Correct 102 ms 2608 KB Ok
62 Correct 133 ms 2932 KB Ok
63 Correct 110 ms 2476 KB Ok
64 Correct 134 ms 2820 KB Ok
65 Correct 132 ms 2780 KB Ok
66 Correct 120 ms 2672 KB Ok
67 Correct 101 ms 2732 KB Ok
68 Correct 112 ms 2784 KB Ok
69 Correct 217 ms 14300 KB Ok
70 Correct 232 ms 15616 KB Ok
71 Correct 212 ms 13344 KB Ok
72 Correct 222 ms 14748 KB Ok
73 Correct 223 ms 12648 KB Ok
74 Correct 211 ms 11708 KB Ok
75 Correct 211 ms 12560 KB Ok
76 Correct 226 ms 15124 KB Ok
77 Correct 208 ms 11824 KB Ok
78 Correct 220 ms 14476 KB Ok
79 Correct 230 ms 14332 KB Ok
80 Correct 214 ms 13536 KB Ok
81 Correct 242 ms 13388 KB Ok
82 Correct 208 ms 13368 KB Ok
83 Correct 209 ms 12500 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 1 ms 300 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 0 ms 212 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 3 ms 468 KB Ok
19 Correct 15 ms 1396 KB Ok
20 Correct 7 ms 828 KB Ok
21 Correct 17 ms 1580 KB Ok
22 Correct 10 ms 980 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 0 ms 212 KB Ok
32 Correct 0 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 0 ms 212 KB Ok
35 Correct 1 ms 212 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 0 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 169 ms 14284 KB Ok
40 Correct 160 ms 20060 KB Ok
41 Correct 310 ms 21508 KB Ok
42 Correct 230 ms 20048 KB Ok
43 Correct 114 ms 9324 KB Ok
44 Correct 193 ms 18428 KB Ok
45 Correct 3 ms 340 KB Ok
46 Correct 3 ms 468 KB Ok
47 Correct 3 ms 340 KB Ok
48 Correct 2 ms 340 KB Ok
49 Correct 2 ms 336 KB Ok
50 Correct 2 ms 340 KB Ok
51 Correct 2 ms 340 KB Ok
52 Correct 3 ms 340 KB Ok
53 Correct 3 ms 340 KB Ok
54 Correct 2 ms 340 KB Ok
55 Correct 6 ms 596 KB Ok
56 Correct 6 ms 724 KB Ok
57 Correct 6 ms 728 KB Ok
58 Correct 6 ms 724 KB Ok
59 Correct 6 ms 724 KB Ok
60 Correct 5 ms 724 KB Ok
61 Correct 6 ms 712 KB Ok
62 Correct 6 ms 724 KB Ok
63 Correct 6 ms 596 KB Ok
64 Correct 6 ms 724 KB Ok
65 Correct 117 ms 2700 KB Ok
66 Correct 141 ms 2916 KB Ok
67 Correct 139 ms 3168 KB Ok
68 Correct 98 ms 2452 KB Ok
69 Correct 126 ms 2748 KB Ok
70 Correct 111 ms 2584 KB Ok
71 Correct 99 ms 2524 KB Ok
72 Correct 102 ms 2608 KB Ok
73 Correct 133 ms 2932 KB Ok
74 Correct 110 ms 2476 KB Ok
75 Correct 134 ms 2820 KB Ok
76 Correct 132 ms 2780 KB Ok
77 Correct 120 ms 2672 KB Ok
78 Correct 101 ms 2732 KB Ok
79 Correct 112 ms 2784 KB Ok
80 Correct 217 ms 14300 KB Ok
81 Correct 232 ms 15616 KB Ok
82 Correct 212 ms 13344 KB Ok
83 Correct 222 ms 14748 KB Ok
84 Correct 223 ms 12648 KB Ok
85 Correct 211 ms 11708 KB Ok
86 Correct 211 ms 12560 KB Ok
87 Correct 226 ms 15124 KB Ok
88 Correct 208 ms 11824 KB Ok
89 Correct 220 ms 14476 KB Ok
90 Correct 230 ms 14332 KB Ok
91 Correct 214 ms 13536 KB Ok
92 Correct 242 ms 13388 KB Ok
93 Correct 208 ms 13368 KB Ok
94 Correct 209 ms 12500 KB Ok
95 Correct 302 ms 6664 KB Ok
96 Correct 438 ms 10676 KB Ok
97 Correct 430 ms 8292 KB Ok
98 Correct 312 ms 7564 KB Ok
99 Correct 382 ms 7952 KB Ok
100 Correct 398 ms 7748 KB Ok
101 Correct 390 ms 8800 KB Ok
102 Correct 381 ms 8752 KB Ok
103 Correct 379 ms 8264 KB Ok
104 Correct 453 ms 9736 KB Ok
105 Correct 455 ms 11092 KB Ok
106 Correct 365 ms 8676 KB Ok
107 Correct 443 ms 9092 KB Ok
108 Correct 467 ms 10320 KB Ok
109 Correct 413 ms 9248 KB Ok
110 Correct 1016 ms 51436 KB Ok
111 Correct 1119 ms 60688 KB Ok
112 Correct 1030 ms 49724 KB Ok
113 Correct 1084 ms 59464 KB Ok
114 Correct 1105 ms 56756 KB Ok
115 Correct 1038 ms 55192 KB Ok
116 Correct 1055 ms 57072 KB Ok
117 Correct 1078 ms 59724 KB Ok
118 Correct 995 ms 55348 KB Ok
119 Correct 1034 ms 60212 KB Ok
120 Correct 1002 ms 54356 KB Ok
121 Correct 1000 ms 55220 KB Ok
122 Correct 999 ms 53496 KB Ok
123 Correct 1086 ms 61292 KB Ok
124 Correct 1028 ms 46244 KB Ok
125 Correct 1107 ms 46400 KB Ok