oj.uz

Submission #682591

# Submission time Handle Problem Language Result Execution time Memory
682591 2023-01-16T14:51:45 Z FedShat Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 43808 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;
}

vector<vector<int>> g; // i -> j means pref[i] > pref[j]
vector<int> used;
bool cycle = 0;

void dfs1(int v) {
    used[v] = 0;
    for (auto u : g[v]) {
        if (used[u] == -1) {
            dfs1(u);
        } else if (used[u] == 0) {
            cycle = 1;
        }
    }
    used[v] = 1;
}

vector<ll> dp;

void dfs2(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs2(u);
        }
        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--) {
        int n, m;
        cin >> n >> m;
        int l = 0, r = n + m;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            g.clear();
            g.resize(mid + 1);
            for (int i = 0; i + m <= mid; ++i) {
                g[i + m].push_back(i);
            }
            for (int i = 0; i + n <= mid; ++i) {
                g[i].push_back(i + n);
            }
            cycle = 0;
            used.assign(mid + 1, -1);
            for (int i = 0; i <= mid; ++i) {
                if (used[i] == -1) {
                    dfs1(i);
                }
            }
            if (!cycle) {
                l = mid;
            } else {
                r = mid;
            }
        }
        g.clear();
        g.resize(l + 1);
        for (int i = 0; i + m <= l; ++i) {
            g[i + m].push_back(i);
        }
        for (int i = 0; i + n <= l; ++i) {
            g[i].push_back(i + n);
        }
        used.assign(l + 1, 0);
        dp.assign(l + 1, 0);
        for (int i = 0; i <= l; ++i) {
            if (!used[i]) {
                dfs2(i);
            }
        }
        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 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 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 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 1 ms 212 KB Ok
6 Correct 9 ms 596 KB Ok
7 Correct 54 ms 1656 KB Ok
8 Correct 22 ms 940 KB Ok
9 Correct 64 ms 1820 KB Ok
10 Correct 33 ms 1232 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 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 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 1 ms 212 KB Ok
6 Correct 639 ms 28700 KB Ok
7 Correct 596 ms 31940 KB Ok
8 Correct 1353 ms 43808 KB Ok
9 Correct 941 ms 32324 KB Ok
10 Correct 505 ms 18232 KB Ok
11 Correct 869 ms 32712 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 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 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 1 ms 212 KB Ok
19 Correct 0 ms 212 KB Ok
20 Correct 0 ms 212 KB Ok
21 Correct 1 ms 212 KB Ok
22 Correct 1 ms 212 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 7 ms 512 KB Ok
25 Correct 8 ms 596 KB Ok
26 Correct 9 ms 556 KB Ok
27 Correct 7 ms 596 KB Ok
28 Correct 6 ms 596 KB Ok
29 Correct 5 ms 464 KB Ok
30 Correct 5 ms 468 KB Ok
31 Correct 8 ms 596 KB Ok
32 Correct 9 ms 596 KB Ok
33 Correct 8 ms 468 KB Ok
34 Correct 19 ms 900 KB Ok
35 Correct 21 ms 1012 KB Ok
36 Correct 20 ms 960 KB Ok
37 Correct 20 ms 1068 KB Ok
38 Correct 19 ms 1052 KB Ok
39 Correct 20 ms 888 KB Ok
40 Correct 26 ms 1008 KB Ok
41 Correct 19 ms 872 KB Ok
42 Correct 20 ms 816 KB Ok
43 Correct 20 ms 964 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 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 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 9 ms 596 KB Ok
19 Correct 54 ms 1656 KB Ok
20 Correct 22 ms 940 KB Ok
21 Correct 64 ms 1820 KB Ok
22 Correct 33 ms 1232 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 7 ms 512 KB Ok
35 Correct 8 ms 596 KB Ok
36 Correct 9 ms 556 KB Ok
37 Correct 7 ms 596 KB Ok
38 Correct 6 ms 596 KB Ok
39 Correct 5 ms 464 KB Ok
40 Correct 5 ms 468 KB Ok
41 Correct 8 ms 596 KB Ok
42 Correct 9 ms 596 KB Ok
43 Correct 8 ms 468 KB Ok
44 Correct 19 ms 900 KB Ok
45 Correct 21 ms 1012 KB Ok
46 Correct 20 ms 960 KB Ok
47 Correct 20 ms 1068 KB Ok
48 Correct 19 ms 1052 KB Ok
49 Correct 20 ms 888 KB Ok
50 Correct 26 ms 1008 KB Ok
51 Correct 19 ms 872 KB Ok
52 Correct 20 ms 816 KB Ok
53 Correct 20 ms 964 KB Ok
54 Correct 450 ms 9400 KB Ok
55 Correct 626 ms 10140 KB Ok
56 Correct 525 ms 10384 KB Ok
57 Correct 352 ms 8560 KB Ok
58 Correct 454 ms 11080 KB Ok
59 Correct 394 ms 9208 KB Ok
60 Correct 334 ms 9060 KB Ok
61 Correct 348 ms 10592 KB Ok
62 Correct 584 ms 9820 KB Ok
63 Correct 377 ms 8256 KB Ok
64 Correct 583 ms 11016 KB Ok
65 Correct 541 ms 9028 KB Ok
66 Correct 530 ms 8628 KB Ok
67 Correct 381 ms 9788 KB Ok
68 Correct 437 ms 9960 KB Ok
69 Correct 1610 ms 22024 KB Ok
70 Correct 1357 ms 24064 KB Ok
71 Correct 1248 ms 22568 KB Ok
72 Correct 1315 ms 24224 KB Ok
73 Correct 1228 ms 22076 KB Ok
74 Correct 1296 ms 18916 KB Ok
75 Correct 1324 ms 17480 KB Ok
76 Correct 1352 ms 23256 KB Ok
77 Correct 1153 ms 22364 KB Ok
78 Correct 1198 ms 23092 KB Ok
79 Correct 1381 ms 22456 KB Ok
80 Correct 1256 ms 23032 KB Ok
81 Correct 1442 ms 21504 KB Ok
82 Correct 1439 ms 20308 KB Ok
83 Correct 1218 ms 19672 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 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 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 9 ms 596 KB Ok
19 Correct 54 ms 1656 KB Ok
20 Correct 22 ms 940 KB Ok
21 Correct 64 ms 1820 KB Ok
22 Correct 33 ms 1232 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 1 ms 212 KB Ok
25 Correct 1 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 1 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 0 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 1 ms 212 KB Ok
35 Correct 0 ms 212 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 1 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 639 ms 28700 KB Ok
40 Correct 596 ms 31940 KB Ok
41 Correct 1353 ms 43808 KB Ok
42 Correct 941 ms 32324 KB Ok
43 Correct 505 ms 18232 KB Ok
44 Correct 869 ms 32712 KB Ok
45 Correct 7 ms 512 KB Ok
46 Correct 8 ms 596 KB Ok
47 Correct 9 ms 556 KB Ok
48 Correct 7 ms 596 KB Ok
49 Correct 6 ms 596 KB Ok
50 Correct 5 ms 464 KB Ok
51 Correct 5 ms 468 KB Ok
52 Correct 8 ms 596 KB Ok
53 Correct 9 ms 596 KB Ok
54 Correct 8 ms 468 KB Ok
55 Correct 19 ms 900 KB Ok
56 Correct 21 ms 1012 KB Ok
57 Correct 20 ms 960 KB Ok
58 Correct 20 ms 1068 KB Ok
59 Correct 19 ms 1052 KB Ok
60 Correct 20 ms 888 KB Ok
61 Correct 26 ms 1008 KB Ok
62 Correct 19 ms 872 KB Ok
63 Correct 20 ms 816 KB Ok
64 Correct 20 ms 964 KB Ok
65 Correct 450 ms 9400 KB Ok
66 Correct 626 ms 10140 KB Ok
67 Correct 525 ms 10384 KB Ok
68 Correct 352 ms 8560 KB Ok
69 Correct 454 ms 11080 KB Ok
70 Correct 394 ms 9208 KB Ok
71 Correct 334 ms 9060 KB Ok
72 Correct 348 ms 10592 KB Ok
73 Correct 584 ms 9820 KB Ok
74 Correct 377 ms 8256 KB Ok
75 Correct 583 ms 11016 KB Ok
76 Correct 541 ms 9028 KB Ok
77 Correct 530 ms 8628 KB Ok
78 Correct 381 ms 9788 KB Ok
79 Correct 437 ms 9960 KB Ok
80 Correct 1610 ms 22024 KB Ok
81 Correct 1357 ms 24064 KB Ok
82 Correct 1248 ms 22568 KB Ok
83 Correct 1315 ms 24224 KB Ok
84 Correct 1228 ms 22076 KB Ok
85 Correct 1296 ms 18916 KB Ok
86 Correct 1324 ms 17480 KB Ok
87 Correct 1352 ms 23256 KB Ok
88 Correct 1153 ms 22364 KB Ok
89 Correct 1198 ms 23092 KB Ok
90 Correct 1381 ms 22456 KB Ok
91 Correct 1256 ms 23032 KB Ok
92 Correct 1442 ms 21504 KB Ok
93 Correct 1439 ms 20308 KB Ok
94 Correct 1218 ms 19672 KB Ok
95 Correct 1428 ms 22124 KB Ok
96 Execution timed out 2071 ms 37972 KB Time limit exceeded
97 Halted 0 ms 0 KB -