oj.uz

Submission #173964

# Submission time Handle Problem Language Result Execution time Memory
173964 2020-01-05T21:45:51 Z mcdx9524 Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 36536 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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 = (l + r) / 2;
        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 68 ms 14584 KB Ok
2 Correct 65 ms 14584 KB Ok
3 Correct 98 ms 14584 KB Ok
4 Correct 99 ms 14584 KB Ok
5 Correct 101 ms 14456 KB Ok
6 Correct 113 ms 14736 KB Ok
7 Correct 96 ms 14456 KB Ok
8 Correct 97 ms 14584 KB Ok
9 Correct 99 ms 14456 KB Ok
10 Correct 101 ms 14456 KB Ok
11 Correct 99 ms 14456 KB Ok
12 Correct 95 ms 14456 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 14456 KB Ok
2 Correct 75 ms 14456 KB Ok
3 Correct 74 ms 14584 KB Ok
4 Correct 76 ms 14608 KB Ok
5 Correct 77 ms 14532 KB Ok
6 Correct 82 ms 14712 KB Ok
7 Correct 102 ms 15608 KB Ok
8 Correct 87 ms 15096 KB Ok
9 Correct 102 ms 15940 KB Ok
10 Correct 89 ms 15224 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14584 KB Ok
2 Correct 63 ms 14712 KB Ok
3 Correct 74 ms 14456 KB Ok
4 Correct 67 ms 14440 KB Ok
5 Correct 74 ms 14584 KB Ok
6 Correct 73 ms 14584 KB Ok
7 Correct 72 ms 14584 KB Ok
8 Correct 72 ms 14584 KB Ok
9 Correct 85 ms 14456 KB Ok
10 Correct 75 ms 14584 KB Ok
11 Correct 73 ms 14584 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14712 KB Ok
2 Correct 79 ms 14560 KB Ok
3 Correct 82 ms 14584 KB Ok
4 Correct 86 ms 14604 KB Ok
5 Correct 91 ms 14684 KB Ok
6 Correct 822 ms 29440 KB Ok
7 Correct 858 ms 33812 KB Ok
8 Correct 1474 ms 36536 KB Ok
9 Correct 1078 ms 34016 KB Ok
10 Correct 618 ms 24616 KB Ok
11 Correct 948 ms 32072 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 14584 KB Ok
2 Correct 65 ms 14584 KB Ok
3 Correct 98 ms 14584 KB Ok
4 Correct 99 ms 14584 KB Ok
5 Correct 101 ms 14456 KB Ok
6 Correct 113 ms 14736 KB Ok
7 Correct 96 ms 14456 KB Ok
8 Correct 97 ms 14584 KB Ok
9 Correct 99 ms 14456 KB Ok
10 Correct 101 ms 14456 KB Ok
11 Correct 99 ms 14456 KB Ok
12 Correct 95 ms 14456 KB Ok
13 Correct 31 ms 14584 KB Ok
14 Correct 63 ms 14712 KB Ok
15 Correct 74 ms 14456 KB Ok
16 Correct 67 ms 14440 KB Ok
17 Correct 74 ms 14584 KB Ok
18 Correct 73 ms 14584 KB Ok
19 Correct 72 ms 14584 KB Ok
20 Correct 72 ms 14584 KB Ok
21 Correct 85 ms 14456 KB Ok
22 Correct 75 ms 14584 KB Ok
23 Correct 73 ms 14584 KB Ok
24 Correct 149 ms 14708 KB Ok
25 Correct 146 ms 14712 KB Ok
26 Correct 153 ms 14980 KB Ok
27 Correct 148 ms 14712 KB Ok
28 Correct 146 ms 14704 KB Ok
29 Correct 146 ms 14712 KB Ok
30 Correct 134 ms 14812 KB Ok
31 Correct 148 ms 14684 KB Ok
32 Correct 149 ms 14712 KB Ok
33 Correct 148 ms 14712 KB Ok
34 Correct 172 ms 14920 KB Ok
35 Correct 170 ms 15096 KB Ok
36 Correct 171 ms 14996 KB Ok
37 Correct 172 ms 14948 KB Ok
38 Correct 170 ms 14968 KB Ok
39 Correct 169 ms 15044 KB Ok
40 Correct 176 ms 14940 KB Ok
41 Correct 170 ms 14912 KB Ok
42 Correct 177 ms 14920 KB Ok
43 Correct 173 ms 15224 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 14584 KB Ok
2 Correct 65 ms 14584 KB Ok
3 Correct 98 ms 14584 KB Ok
4 Correct 99 ms 14584 KB Ok
5 Correct 101 ms 14456 KB Ok
6 Correct 113 ms 14736 KB Ok
7 Correct 96 ms 14456 KB Ok
8 Correct 97 ms 14584 KB Ok
9 Correct 99 ms 14456 KB Ok
10 Correct 101 ms 14456 KB Ok
11 Correct 99 ms 14456 KB Ok
12 Correct 95 ms 14456 KB Ok
13 Correct 79 ms 14456 KB Ok
14 Correct 75 ms 14456 KB Ok
15 Correct 74 ms 14584 KB Ok
16 Correct 76 ms 14608 KB Ok
17 Correct 77 ms 14532 KB Ok
18 Correct 82 ms 14712 KB Ok
19 Correct 102 ms 15608 KB Ok
20 Correct 87 ms 15096 KB Ok
21 Correct 102 ms 15940 KB Ok
22 Correct 89 ms 15224 KB Ok
23 Correct 31 ms 14584 KB Ok
24 Correct 63 ms 14712 KB Ok
25 Correct 74 ms 14456 KB Ok
26 Correct 67 ms 14440 KB Ok
27 Correct 74 ms 14584 KB Ok
28 Correct 73 ms 14584 KB Ok
29 Correct 72 ms 14584 KB Ok
30 Correct 72 ms 14584 KB Ok
31 Correct 85 ms 14456 KB Ok
32 Correct 75 ms 14584 KB Ok
33 Correct 73 ms 14584 KB Ok
34 Correct 149 ms 14708 KB Ok
35 Correct 146 ms 14712 KB Ok
36 Correct 153 ms 14980 KB Ok
37 Correct 148 ms 14712 KB Ok
38 Correct 146 ms 14704 KB Ok
39 Correct 146 ms 14712 KB Ok
40 Correct 134 ms 14812 KB Ok
41 Correct 148 ms 14684 KB Ok
42 Correct 149 ms 14712 KB Ok
43 Correct 148 ms 14712 KB Ok
44 Correct 172 ms 14920 KB Ok
45 Correct 170 ms 15096 KB Ok
46 Correct 171 ms 14996 KB Ok
47 Correct 172 ms 14948 KB Ok
48 Correct 170 ms 14968 KB Ok
49 Correct 169 ms 15044 KB Ok
50 Correct 176 ms 14940 KB Ok
51 Correct 170 ms 14912 KB Ok
52 Correct 177 ms 14920 KB Ok
53 Correct 173 ms 15224 KB Ok
54 Correct 698 ms 20096 KB Ok
55 Correct 799 ms 20236 KB Ok
56 Correct 890 ms 20380 KB Ok
57 Correct 528 ms 19392 KB Ok
58 Correct 650 ms 19704 KB Ok
59 Correct 572 ms 19436 KB Ok
60 Correct 484 ms 18948 KB Ok
61 Correct 568 ms 19612 KB Ok
62 Correct 658 ms 20084 KB Ok
63 Correct 594 ms 19516 KB Ok
64 Correct 810 ms 20288 KB Ok
65 Correct 624 ms 19940 KB Ok
66 Correct 589 ms 19852 KB Ok
67 Correct 572 ms 19448 KB Ok
68 Correct 617 ms 19700 KB Ok
69 Correct 1801 ms 29100 KB Ok
70 Correct 1688 ms 29776 KB Ok
71 Correct 1723 ms 29260 KB Ok
72 Correct 1766 ms 29040 KB Ok
73 Correct 1451 ms 28304 KB Ok
74 Correct 1780 ms 28036 KB Ok
75 Execution timed out 2050 ms 26484 KB Time limit exceeded
76 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 14584 KB Ok
2 Correct 65 ms 14584 KB Ok
3 Correct 98 ms 14584 KB Ok
4 Correct 99 ms 14584 KB Ok
5 Correct 101 ms 14456 KB Ok
6 Correct 113 ms 14736 KB Ok
7 Correct 96 ms 14456 KB Ok
8 Correct 97 ms 14584 KB Ok
9 Correct 99 ms 14456 KB Ok
10 Correct 101 ms 14456 KB Ok
11 Correct 99 ms 14456 KB Ok
12 Correct 95 ms 14456 KB Ok
13 Correct 79 ms 14456 KB Ok
14 Correct 75 ms 14456 KB Ok
15 Correct 74 ms 14584 KB Ok
16 Correct 76 ms 14608 KB Ok
17 Correct 77 ms 14532 KB Ok
18 Correct 82 ms 14712 KB Ok
19 Correct 102 ms 15608 KB Ok
20 Correct 87 ms 15096 KB Ok
21 Correct 102 ms 15940 KB Ok
22 Correct 89 ms 15224 KB Ok
23 Correct 31 ms 14584 KB Ok
24 Correct 63 ms 14712 KB Ok
25 Correct 74 ms 14456 KB Ok
26 Correct 67 ms 14440 KB Ok
27 Correct 74 ms 14584 KB Ok
28 Correct 73 ms 14584 KB Ok
29 Correct 72 ms 14584 KB Ok
30 Correct 72 ms 14584 KB Ok
31 Correct 85 ms 14456 KB Ok
32 Correct 75 ms 14584 KB Ok
33 Correct 73 ms 14584 KB Ok
34 Correct 72 ms 14712 KB Ok
35 Correct 79 ms 14560 KB Ok
36 Correct 82 ms 14584 KB Ok
37 Correct 86 ms 14604 KB Ok
38 Correct 91 ms 14684 KB Ok
39 Correct 822 ms 29440 KB Ok
40 Correct 858 ms 33812 KB Ok
41 Correct 1474 ms 36536 KB Ok
42 Correct 1078 ms 34016 KB Ok
43 Correct 618 ms 24616 KB Ok
44 Correct 948 ms 32072 KB Ok
45 Correct 149 ms 14708 KB Ok
46 Correct 146 ms 14712 KB Ok
47 Correct 153 ms 14980 KB Ok
48 Correct 148 ms 14712 KB Ok
49 Correct 146 ms 14704 KB Ok
50 Correct 146 ms 14712 KB Ok
51 Correct 134 ms 14812 KB Ok
52 Correct 148 ms 14684 KB Ok
53 Correct 149 ms 14712 KB Ok
54 Correct 148 ms 14712 KB Ok
55 Correct 172 ms 14920 KB Ok
56 Correct 170 ms 15096 KB Ok
57 Correct 171 ms 14996 KB Ok
58 Correct 172 ms 14948 KB Ok
59 Correct 170 ms 14968 KB Ok
60 Correct 169 ms 15044 KB Ok
61 Correct 176 ms 14940 KB Ok
62 Correct 170 ms 14912 KB Ok
63 Correct 177 ms 14920 KB Ok
64 Correct 173 ms 15224 KB Ok
65 Correct 698 ms 20096 KB Ok
66 Correct 799 ms 20236 KB Ok
67 Correct 890 ms 20380 KB Ok
68 Correct 528 ms 19392 KB Ok
69 Correct 650 ms 19704 KB Ok
70 Correct 572 ms 19436 KB Ok
71 Correct 484 ms 18948 KB Ok
72 Correct 568 ms 19612 KB Ok
73 Correct 658 ms 20084 KB Ok
74 Correct 594 ms 19516 KB Ok
75 Correct 810 ms 20288 KB Ok
76 Correct 624 ms 19940 KB Ok
77 Correct 589 ms 19852 KB Ok
78 Correct 572 ms 19448 KB Ok
79 Correct 617 ms 19700 KB Ok
80 Correct 1801 ms 29100 KB Ok
81 Correct 1688 ms 29776 KB Ok
82 Correct 1723 ms 29260 KB Ok
83 Correct 1766 ms 29040 KB Ok
84 Correct 1451 ms 28304 KB Ok
85 Correct 1780 ms 28036 KB Ok
86 Execution timed out 2050 ms 26484 KB Time limit exceeded
87 Halted 0 ms 0 KB -