oj.uz

Submission #173967

# Submission time Handle Problem Language Result Execution time Memory
173967 2020-01-05T21:56:32 Z mcdx9524 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 36540 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution<int> (l, r) (rnd);
}

const int N = 5e5 + 7;

int n, m;
vector <int> p;
vector <int> ord;
vector <int> g[N];
bool used[N];
int col[N];

bool cycle(int v) {
    col[v] = 1;
    for (int u : g[v]) {
        if (col[u] == 0) {
            if (cycle(u)) {
                return true;
            }
        } else if (col[u] == 1) {
            return true;
        }
    }
    col[v] = 2;
    return false;
}

void dfs(int v) {
    if (used[v] == true) {
        return;
    }
    used[v] = true;
    for (int u : g[v]) {
        dfs(u);
    }
    ord.push_back(v);
}

bool build(int sz) {
    ord.clear();
    for (int i = 0; i < N; i++) {
        g[i].clear();
        used[i] = false;
        col[i] = 0;
    }
    for (int i = 1; i <= sz; i++) {
        // p[i] - p[i - n] < 0
        // p[i] < p[i - n]
        if (i - n >= 0) {
            g[i - n].push_back(i);
        }
        // p[i] > p[i - m]
        if (i - m >= 0) {
            g[i].push_back(i - m);
        }
    }
    for (int i = 0; i <= sz; i++) {
        if (cycle(i)) {
            return false;
        }
    }
    for (int i = 0; i <= sz; i++) {
        dfs(i);
    }
    p.resize(sz + 1, 0);
    int cur = sz;
    reverse(ord.begin(), ord.end());
    for (int x : ord) {
        p[x] = cur--;
    }
    for (int i = 0; i <= sz; i++) {
        if (!p[i]) {
            p[i] = cur--;
        }
    }
    return true;
}

void solve() {
    cin >> n >> m;
    int l = max(n, m) - 1, r = n + m + 7;
    int ans = l;
    while (l <= r) {
        int md = rand(l, r);
        if (build(md)) {
            l = md + 1;
            ans = md;
        } else {
            r = md - 1;
        }
    }
    build(ans);
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++) {
        cout << p[i] - p[i - 1] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 14584 KB Ok
2 Correct 72 ms 14456 KB Ok
3 Correct 87 ms 14712 KB Ok
4 Correct 87 ms 14456 KB Ok
5 Correct 84 ms 14584 KB Ok
6 Correct 82 ms 14584 KB Ok
7 Correct 85 ms 14584 KB Ok
8 Correct 90 ms 14584 KB Ok
9 Correct 98 ms 14628 KB Ok
10 Correct 87 ms 14608 KB Ok
11 Correct 101 ms 14584 KB Ok
12 Correct 86 ms 14584 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 14456 KB Ok
2 Correct 80 ms 14584 KB Ok
3 Correct 79 ms 14584 KB Ok
4 Correct 77 ms 14584 KB Ok
5 Correct 71 ms 14584 KB Ok
6 Correct 77 ms 14840 KB Ok
7 Correct 89 ms 15608 KB Ok
8 Correct 81 ms 15096 KB Ok
9 Correct 95 ms 15736 KB Ok
10 Correct 99 ms 15224 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14456 KB Ok
2 Correct 91 ms 14604 KB Ok
3 Correct 77 ms 14604 KB Ok
4 Correct 72 ms 14584 KB Ok
5 Correct 86 ms 14584 KB Ok
6 Correct 77 ms 14564 KB Ok
7 Correct 81 ms 14596 KB Ok
8 Correct 108 ms 14608 KB Ok
9 Correct 92 ms 14584 KB Ok
10 Correct 92 ms 14696 KB Ok
11 Correct 91 ms 14584 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 14584 KB Ok
2 Correct 99 ms 14604 KB Ok
3 Correct 149 ms 14584 KB Ok
4 Correct 112 ms 14584 KB Ok
5 Correct 93 ms 14456 KB Ok
6 Correct 794 ms 29336 KB Ok
7 Correct 723 ms 33904 KB Ok
8 Correct 1206 ms 36540 KB Ok
9 Correct 901 ms 33848 KB Ok
10 Correct 565 ms 24516 KB Ok
11 Correct 738 ms 32212 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 14584 KB Ok
2 Correct 72 ms 14456 KB Ok
3 Correct 87 ms 14712 KB Ok
4 Correct 87 ms 14456 KB Ok
5 Correct 84 ms 14584 KB Ok
6 Correct 82 ms 14584 KB Ok
7 Correct 85 ms 14584 KB Ok
8 Correct 90 ms 14584 KB Ok
9 Correct 98 ms 14628 KB Ok
10 Correct 87 ms 14608 KB Ok
11 Correct 101 ms 14584 KB Ok
12 Correct 86 ms 14584 KB Ok
13 Correct 29 ms 14456 KB Ok
14 Correct 91 ms 14604 KB Ok
15 Correct 77 ms 14604 KB Ok
16 Correct 72 ms 14584 KB Ok
17 Correct 86 ms 14584 KB Ok
18 Correct 77 ms 14564 KB Ok
19 Correct 81 ms 14596 KB Ok
20 Correct 108 ms 14608 KB Ok
21 Correct 92 ms 14584 KB Ok
22 Correct 92 ms 14696 KB Ok
23 Correct 91 ms 14584 KB Ok
24 Correct 153 ms 14712 KB Ok
25 Correct 163 ms 14768 KB Ok
26 Correct 163 ms 14848 KB Ok
27 Correct 145 ms 14712 KB Ok
28 Correct 138 ms 14840 KB Ok
29 Correct 171 ms 14692 KB Ok
30 Correct 166 ms 14732 KB Ok
31 Correct 155 ms 14736 KB Ok
32 Correct 181 ms 14736 KB Ok
33 Correct 165 ms 14788 KB Ok
34 Correct 181 ms 14968 KB Ok
35 Correct 169 ms 15084 KB Ok
36 Correct 180 ms 15024 KB Ok
37 Correct 163 ms 15044 KB Ok
38 Correct 173 ms 14928 KB Ok
39 Correct 181 ms 14968 KB Ok
40 Correct 199 ms 15096 KB Ok
41 Correct 176 ms 14956 KB Ok
42 Correct 172 ms 14968 KB Ok
43 Correct 191 ms 15012 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 14584 KB Ok
2 Correct 72 ms 14456 KB Ok
3 Correct 87 ms 14712 KB Ok
4 Correct 87 ms 14456 KB Ok
5 Correct 84 ms 14584 KB Ok
6 Correct 82 ms 14584 KB Ok
7 Correct 85 ms 14584 KB Ok
8 Correct 90 ms 14584 KB Ok
9 Correct 98 ms 14628 KB Ok
10 Correct 87 ms 14608 KB Ok
11 Correct 101 ms 14584 KB Ok
12 Correct 86 ms 14584 KB Ok
13 Correct 74 ms 14456 KB Ok
14 Correct 80 ms 14584 KB Ok
15 Correct 79 ms 14584 KB Ok
16 Correct 77 ms 14584 KB Ok
17 Correct 71 ms 14584 KB Ok
18 Correct 77 ms 14840 KB Ok
19 Correct 89 ms 15608 KB Ok
20 Correct 81 ms 15096 KB Ok
21 Correct 95 ms 15736 KB Ok
22 Correct 99 ms 15224 KB Ok
23 Correct 29 ms 14456 KB Ok
24 Correct 91 ms 14604 KB Ok
25 Correct 77 ms 14604 KB Ok
26 Correct 72 ms 14584 KB Ok
27 Correct 86 ms 14584 KB Ok
28 Correct 77 ms 14564 KB Ok
29 Correct 81 ms 14596 KB Ok
30 Correct 108 ms 14608 KB Ok
31 Correct 92 ms 14584 KB Ok
32 Correct 92 ms 14696 KB Ok
33 Correct 91 ms 14584 KB Ok
34 Correct 153 ms 14712 KB Ok
35 Correct 163 ms 14768 KB Ok
36 Correct 163 ms 14848 KB Ok
37 Correct 145 ms 14712 KB Ok
38 Correct 138 ms 14840 KB Ok
39 Correct 171 ms 14692 KB Ok
40 Correct 166 ms 14732 KB Ok
41 Correct 155 ms 14736 KB Ok
42 Correct 181 ms 14736 KB Ok
43 Correct 165 ms 14788 KB Ok
44 Correct 181 ms 14968 KB Ok
45 Correct 169 ms 15084 KB Ok
46 Correct 180 ms 15024 KB Ok
47 Correct 163 ms 15044 KB Ok
48 Correct 173 ms 14928 KB Ok
49 Correct 181 ms 14968 KB Ok
50 Correct 199 ms 15096 KB Ok
51 Correct 176 ms 14956 KB Ok
52 Correct 172 ms 14968 KB Ok
53 Correct 191 ms 15012 KB Ok
54 Correct 746 ms 19920 KB Ok
55 Correct 988 ms 20324 KB Ok
56 Correct 978 ms 20456 KB Ok
57 Correct 640 ms 19248 KB Ok
58 Correct 691 ms 19832 KB Ok
59 Correct 605 ms 19608 KB Ok
60 Correct 630 ms 19108 KB Ok
61 Correct 595 ms 19596 KB Ok
62 Correct 803 ms 20048 KB Ok
63 Correct 672 ms 19352 KB Ok
64 Correct 782 ms 20272 KB Ok
65 Correct 741 ms 19904 KB Ok
66 Correct 670 ms 19720 KB Ok
67 Correct 638 ms 19440 KB Ok
68 Correct 596 ms 19772 KB Ok
69 Correct 1765 ms 29208 KB Ok
70 Correct 1702 ms 29740 KB Ok
71 Correct 1814 ms 29004 KB Ok
72 Correct 1815 ms 29188 KB Ok
73 Correct 1378 ms 28328 KB Ok
74 Correct 1568 ms 28108 KB Ok
75 Correct 1632 ms 28492 KB Ok
76 Correct 1812 ms 29284 KB Ok
77 Correct 1463 ms 27636 KB Ok
78 Correct 1629 ms 27936 KB Ok
79 Correct 1857 ms 28820 KB Ok
80 Correct 1562 ms 29104 KB Ok
81 Correct 1966 ms 28320 KB Ok
82 Correct 1487 ms 29116 KB Ok
83 Correct 1516 ms 28260 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 14584 KB Ok
2 Correct 72 ms 14456 KB Ok
3 Correct 87 ms 14712 KB Ok
4 Correct 87 ms 14456 KB Ok
5 Correct 84 ms 14584 KB Ok
6 Correct 82 ms 14584 KB Ok
7 Correct 85 ms 14584 KB Ok
8 Correct 90 ms 14584 KB Ok
9 Correct 98 ms 14628 KB Ok
10 Correct 87 ms 14608 KB Ok
11 Correct 101 ms 14584 KB Ok
12 Correct 86 ms 14584 KB Ok
13 Correct 74 ms 14456 KB Ok
14 Correct 80 ms 14584 KB Ok
15 Correct 79 ms 14584 KB Ok
16 Correct 77 ms 14584 KB Ok
17 Correct 71 ms 14584 KB Ok
18 Correct 77 ms 14840 KB Ok
19 Correct 89 ms 15608 KB Ok
20 Correct 81 ms 15096 KB Ok
21 Correct 95 ms 15736 KB Ok
22 Correct 99 ms 15224 KB Ok
23 Correct 29 ms 14456 KB Ok
24 Correct 91 ms 14604 KB Ok
25 Correct 77 ms 14604 KB Ok
26 Correct 72 ms 14584 KB Ok
27 Correct 86 ms 14584 KB Ok
28 Correct 77 ms 14564 KB Ok
29 Correct 81 ms 14596 KB Ok
30 Correct 108 ms 14608 KB Ok
31 Correct 92 ms 14584 KB Ok
32 Correct 92 ms 14696 KB Ok
33 Correct 91 ms 14584 KB Ok
34 Correct 80 ms 14584 KB Ok
35 Correct 99 ms 14604 KB Ok
36 Correct 149 ms 14584 KB Ok
37 Correct 112 ms 14584 KB Ok
38 Correct 93 ms 14456 KB Ok
39 Correct 794 ms 29336 KB Ok
40 Correct 723 ms 33904 KB Ok
41 Correct 1206 ms 36540 KB Ok
42 Correct 901 ms 33848 KB Ok
43 Correct 565 ms 24516 KB Ok
44 Correct 738 ms 32212 KB Ok
45 Correct 153 ms 14712 KB Ok
46 Correct 163 ms 14768 KB Ok
47 Correct 163 ms 14848 KB Ok
48 Correct 145 ms 14712 KB Ok
49 Correct 138 ms 14840 KB Ok
50 Correct 171 ms 14692 KB Ok
51 Correct 166 ms 14732 KB Ok
52 Correct 155 ms 14736 KB Ok
53 Correct 181 ms 14736 KB Ok
54 Correct 165 ms 14788 KB Ok
55 Correct 181 ms 14968 KB Ok
56 Correct 169 ms 15084 KB Ok
57 Correct 180 ms 15024 KB Ok
58 Correct 163 ms 15044 KB Ok
59 Correct 173 ms 14928 KB Ok
60 Correct 181 ms 14968 KB Ok
61 Correct 199 ms 15096 KB Ok
62 Correct 176 ms 14956 KB Ok
63 Correct 172 ms 14968 KB Ok
64 Correct 191 ms 15012 KB Ok
65 Correct 746 ms 19920 KB Ok
66 Correct 988 ms 20324 KB Ok
67 Correct 978 ms 20456 KB Ok
68 Correct 640 ms 19248 KB Ok
69 Correct 691 ms 19832 KB Ok
70 Correct 605 ms 19608 KB Ok
71 Correct 630 ms 19108 KB Ok
72 Correct 595 ms 19596 KB Ok
73 Correct 803 ms 20048 KB Ok
74 Correct 672 ms 19352 KB Ok
75 Correct 782 ms 20272 KB Ok
76 Correct 741 ms 19904 KB Ok
77 Correct 670 ms 19720 KB Ok
78 Correct 638 ms 19440 KB Ok
79 Correct 596 ms 19772 KB Ok
80 Correct 1765 ms 29208 KB Ok
81 Correct 1702 ms 29740 KB Ok
82 Correct 1814 ms 29004 KB Ok
83 Correct 1815 ms 29188 KB Ok
84 Correct 1378 ms 28328 KB Ok
85 Correct 1568 ms 28108 KB Ok
86 Correct 1632 ms 28492 KB Ok
87 Correct 1812 ms 29284 KB Ok
88 Correct 1463 ms 27636 KB Ok
89 Correct 1629 ms 27936 KB Ok
90 Correct 1857 ms 28820 KB Ok
91 Correct 1562 ms 29104 KB Ok
92 Correct 1966 ms 28320 KB Ok
93 Correct 1487 ms 29116 KB Ok
94 Correct 1516 ms 28260 KB Ok
95 Correct 1400 ms 29028 KB Ok
96 Execution timed out 2067 ms 29260 KB Time limit exceeded
97 Halted 0 ms 0 KB -