oj.uz

답안 #1035741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035741 2024-07-26T14:23:07 Z phoenix Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 63044 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500500;

int n, m;

vector<int> g[N];
int color[N];
bool cycle;

void dfs(int s) {
    color[s] = 1;
    for (int to : g[s]) {
        if (!color[to]) dfs(to);
        cycle |= (color[to] == 1);
    }
    color[s] = 2;
}

void build(int len) {
    for (int i = 0; i <= len; i++) {
        g[i].clear();
        color[i] = 0;
    }
    for (int i = 0; i <= len - n; i++) {
        g[i].push_back(i + n);
    }
    for (int i = 0; i <= len - m; i++) {
        g[i + m].push_back(i);
    }
}

vector<int> top;
void topsort(int s) {
    color[s] = 1;
    for (int to : g[s]) if (!color[to]) {
        topsort(to);
    }
    top.push_back(s);
}

bool check(int len) {
    build(len);
    cycle = false;
    for (int i = 0; i <= len; i++) {
        if (color[i]) continue;
        dfs(i);
        if (cycle) return true;
    }
    return false;
}

void solve() {
    cin >> n >> m;
    int l = 0, r = N;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else 
            l = mid;
    }
    int len = l;
    for (int i = 0; i <= len; i++) color[i] = 0;
    top.clear();
    for (int i = 0; i <= len; i++) if (!color[i])
        topsort(i);
    
    int arr[len + 1] = {};
    for (int i = 0; i <= len; i++) {
        arr[top[i]] = i;
    }
    cout << len << '\n';
    for (int i = 1; i <= len; i++)
        cout << arr[i] - arr[i - 1] << ' ';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t --> 0) {
        solve();
        cout << '\n';
    }
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 32592 KB Ok
2 Correct 79 ms 32600 KB Ok
3 Correct 36 ms 21700 KB Ok
4 Correct 39 ms 21852 KB Ok
5 Correct 38 ms 21792 KB Ok
6 Correct 38 ms 23744 KB Ok
7 Correct 36 ms 21584 KB Ok
8 Correct 39 ms 23900 KB Ok
9 Correct 35 ms 21340 KB Ok
10 Correct 41 ms 26884 KB Ok
11 Correct 42 ms 21596 KB Ok
12 Correct 35 ms 21304 KB Ok

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 26716 KB Ok
2 Correct 63 ms 26712 KB Ok
3 Correct 86 ms 26816 KB Ok
4 Correct 70 ms 26796 KB Ok
5 Correct 64 ms 26880 KB Ok
6 Correct 68 ms 26988 KB Ok
7 Correct 79 ms 27476 KB Ok
8 Correct 71 ms 27060 KB Ok
9 Correct 78 ms 27476 KB Ok
10 Correct 68 ms 27216 KB Ok

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 32592 KB Ok
2 Correct 84 ms 32604 KB Ok
3 Correct 67 ms 26712 KB Ok
4 Correct 65 ms 24924 KB Ok
5 Correct 66 ms 32756 KB Ok
6 Correct 71 ms 32596 KB Ok
7 Correct 64 ms 32600 KB Ok
8 Correct 73 ms 32692 KB Ok
9 Correct 65 ms 32600 KB Ok
10 Correct 65 ms 26728 KB Ok
11 Correct 58 ms 24724 KB Ok

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 26880 KB Ok
2 Correct 67 ms 22564 KB Ok
3 Correct 70 ms 21820 KB Ok
4 Correct 71 ms 21588 KB Ok
5 Correct 70 ms 21340 KB Ok
6 Correct 204 ms 32204 KB Ok
7 Correct 205 ms 33228 KB Ok
8 Correct 322 ms 35800 KB Ok
9 Correct 252 ms 34252 KB Ok
10 Correct 155 ms 27344 KB Ok
11 Correct 242 ms 34504 KB Ok

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 32592 KB Ok
2 Correct 79 ms 32600 KB Ok
3 Correct 36 ms 21700 KB Ok
4 Correct 39 ms 21852 KB Ok
5 Correct 38 ms 21792 KB Ok
6 Correct 38 ms 23744 KB Ok
7 Correct 36 ms 21584 KB Ok
8 Correct 39 ms 23900 KB Ok
9 Correct 35 ms 21340 KB Ok
10 Correct 41 ms 26884 KB Ok
11 Correct 42 ms 21596 KB Ok
12 Correct 35 ms 21304 KB Ok
13 Correct 41 ms 32592 KB Ok
14 Correct 84 ms 32604 KB Ok
15 Correct 67 ms 26712 KB Ok
16 Correct 65 ms 24924 KB Ok
17 Correct 66 ms 32756 KB Ok
18 Correct 71 ms 32596 KB Ok
19 Correct 64 ms 32600 KB Ok
20 Correct 73 ms 32692 KB Ok
21 Correct 65 ms 32600 KB Ok
22 Correct 65 ms 26728 KB Ok
23 Correct 58 ms 24724 KB Ok
24 Correct 36 ms 21076 KB Ok
25 Correct 37 ms 21072 KB Ok
26 Correct 36 ms 21000 KB Ok
27 Correct 37 ms 21056 KB Ok
28 Correct 39 ms 21076 KB Ok
29 Correct 38 ms 21072 KB Ok
30 Correct 36 ms 21072 KB Ok
31 Correct 36 ms 21084 KB Ok
32 Correct 36 ms 21084 KB Ok
33 Correct 37 ms 21072 KB Ok
34 Correct 83 ms 21316 KB Ok
35 Correct 130 ms 21332 KB Ok
36 Correct 97 ms 21240 KB Ok
37 Correct 133 ms 21224 KB Ok
38 Correct 112 ms 21284 KB Ok
39 Correct 79 ms 21328 KB Ok
40 Correct 119 ms 21224 KB Ok
41 Correct 131 ms 21340 KB Ok
42 Correct 91 ms 21248 KB Ok
43 Correct 129 ms 21332 KB Ok

Subtask #6
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 32592 KB Ok
2 Correct 79 ms 32600 KB Ok
3 Correct 36 ms 21700 KB Ok
4 Correct 39 ms 21852 KB Ok
5 Correct 38 ms 21792 KB Ok
6 Correct 38 ms 23744 KB Ok
7 Correct 36 ms 21584 KB Ok
8 Correct 39 ms 23900 KB Ok
9 Correct 35 ms 21340 KB Ok
10 Correct 41 ms 26884 KB Ok
11 Correct 42 ms 21596 KB Ok
12 Correct 35 ms 21304 KB Ok
13 Correct 68 ms 26716 KB Ok
14 Correct 63 ms 26712 KB Ok
15 Correct 86 ms 26816 KB Ok
16 Correct 70 ms 26796 KB Ok
17 Correct 64 ms 26880 KB Ok
18 Correct 68 ms 26988 KB Ok
19 Correct 79 ms 27476 KB Ok
20 Correct 71 ms 27060 KB Ok
21 Correct 78 ms 27476 KB Ok
22 Correct 68 ms 27216 KB Ok
23 Correct 41 ms 32592 KB Ok
24 Correct 84 ms 32604 KB Ok
25 Correct 67 ms 26712 KB Ok
26 Correct 65 ms 24924 KB Ok
27 Correct 66 ms 32756 KB Ok
28 Correct 71 ms 32596 KB Ok
29 Correct 64 ms 32600 KB Ok
30 Correct 73 ms 32692 KB Ok
31 Correct 65 ms 32600 KB Ok
32 Correct 65 ms 26728 KB Ok
33 Correct 58 ms 24724 KB Ok
34 Correct 36 ms 21076 KB Ok
35 Correct 37 ms 21072 KB Ok
36 Correct 36 ms 21000 KB Ok
37 Correct 37 ms 21056 KB Ok
38 Correct 39 ms 21076 KB Ok
39 Correct 38 ms 21072 KB Ok
40 Correct 36 ms 21072 KB Ok
41 Correct 36 ms 21084 KB Ok
42 Correct 36 ms 21084 KB Ok
43 Correct 37 ms 21072 KB Ok
44 Correct 83 ms 21316 KB Ok
45 Correct 130 ms 21332 KB Ok
46 Correct 97 ms 21240 KB Ok
47 Correct 133 ms 21224 KB Ok
48 Correct 112 ms 21284 KB Ok
49 Correct 79 ms 21328 KB Ok
50 Correct 119 ms 21224 KB Ok
51 Correct 131 ms 21340 KB Ok
52 Correct 91 ms 21248 KB Ok
53 Correct 129 ms 21332 KB Ok
54 Correct 124 ms 23348 KB Ok
55 Correct 147 ms 23760 KB Ok
56 Correct 144 ms 23760 KB Ok
57 Correct 94 ms 22992 KB Ok
58 Correct 107 ms 23248 KB Ok
59 Correct 122 ms 22996 KB Ok
60 Correct 90 ms 22736 KB Ok
61 Correct 104 ms 22992 KB Ok
62 Correct 119 ms 23520 KB Ok
63 Correct 107 ms 23076 KB Ok
64 Correct 135 ms 23760 KB Ok
65 Correct 108 ms 23476 KB Ok
66 Correct 107 ms 23248 KB Ok
67 Correct 97 ms 23120 KB Ok
68 Correct 106 ms 23196 KB Ok
69 Correct 697 ms 32116 KB Ok
70 Correct 846 ms 32716 KB Ok
71 Correct 619 ms 32200 KB Ok
72 Correct 695 ms 31956 KB Ok
73 Correct 605 ms 32212 KB Ok
74 Correct 583 ms 31984 KB Ok
75 Correct 640 ms 31700 KB Ok
76 Correct 796 ms 32464 KB Ok
77 Correct 512 ms 31700 KB Ok
78 Correct 766 ms 32208 KB Ok
79 Correct 663 ms 32472 KB Ok
80 Correct 608 ms 32476 KB Ok
81 Correct 708 ms 32208 KB Ok
82 Correct 659 ms 32200 KB Ok
83 Correct 590 ms 31700 KB Ok

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 32592 KB Ok
2 Correct 79 ms 32600 KB Ok
3 Correct 36 ms 21700 KB Ok
4 Correct 39 ms 21852 KB Ok
5 Correct 38 ms 21792 KB Ok
6 Correct 38 ms 23744 KB Ok
7 Correct 36 ms 21584 KB Ok
8 Correct 39 ms 23900 KB Ok
9 Correct 35 ms 21340 KB Ok
10 Correct 41 ms 26884 KB Ok
11 Correct 42 ms 21596 KB Ok
12 Correct 35 ms 21304 KB Ok
13 Correct 68 ms 26716 KB Ok
14 Correct 63 ms 26712 KB Ok
15 Correct 86 ms 26816 KB Ok
16 Correct 70 ms 26796 KB Ok
17 Correct 64 ms 26880 KB Ok
18 Correct 68 ms 26988 KB Ok
19 Correct 79 ms 27476 KB Ok
20 Correct 71 ms 27060 KB Ok
21 Correct 78 ms 27476 KB Ok
22 Correct 68 ms 27216 KB Ok
23 Correct 41 ms 32592 KB Ok
24 Correct 84 ms 32604 KB Ok
25 Correct 67 ms 26712 KB Ok
26 Correct 65 ms 24924 KB Ok
27 Correct 66 ms 32756 KB Ok
28 Correct 71 ms 32596 KB Ok
29 Correct 64 ms 32600 KB Ok
30 Correct 73 ms 32692 KB Ok
31 Correct 65 ms 32600 KB Ok
32 Correct 65 ms 26728 KB Ok
33 Correct 58 ms 24724 KB Ok
34 Correct 66 ms 26880 KB Ok
35 Correct 67 ms 22564 KB Ok
36 Correct 70 ms 21820 KB Ok
37 Correct 71 ms 21588 KB Ok
38 Correct 70 ms 21340 KB Ok
39 Correct 204 ms 32204 KB Ok
40 Correct 205 ms 33228 KB Ok
41 Correct 322 ms 35800 KB Ok
42 Correct 252 ms 34252 KB Ok
43 Correct 155 ms 27344 KB Ok
44 Correct 242 ms 34504 KB Ok
45 Correct 36 ms 21076 KB Ok
46 Correct 37 ms 21072 KB Ok
47 Correct 36 ms 21000 KB Ok
48 Correct 37 ms 21056 KB Ok
49 Correct 39 ms 21076 KB Ok
50 Correct 38 ms 21072 KB Ok
51 Correct 36 ms 21072 KB Ok
52 Correct 36 ms 21084 KB Ok
53 Correct 36 ms 21084 KB Ok
54 Correct 37 ms 21072 KB Ok
55 Correct 83 ms 21316 KB Ok
56 Correct 130 ms 21332 KB Ok
57 Correct 97 ms 21240 KB Ok
58 Correct 133 ms 21224 KB Ok
59 Correct 112 ms 21284 KB Ok
60 Correct 79 ms 21328 KB Ok
61 Correct 119 ms 21224 KB Ok
62 Correct 131 ms 21340 KB Ok
63 Correct 91 ms 21248 KB Ok
64 Correct 129 ms 21332 KB Ok
65 Correct 124 ms 23348 KB Ok
66 Correct 147 ms 23760 KB Ok
67 Correct 144 ms 23760 KB Ok
68 Correct 94 ms 22992 KB Ok
69 Correct 107 ms 23248 KB Ok
70 Correct 122 ms 22996 KB Ok
71 Correct 90 ms 22736 KB Ok
72 Correct 104 ms 22992 KB Ok
73 Correct 119 ms 23520 KB Ok
74 Correct 107 ms 23076 KB Ok
75 Correct 135 ms 23760 KB Ok
76 Correct 108 ms 23476 KB Ok
77 Correct 107 ms 23248 KB Ok
78 Correct 97 ms 23120 KB Ok
79 Correct 106 ms 23196 KB Ok
80 Correct 697 ms 32116 KB Ok
81 Correct 846 ms 32716 KB Ok
82 Correct 619 ms 32200 KB Ok
83 Correct 695 ms 31956 KB Ok
84 Correct 605 ms 32212 KB Ok
85 Correct 583 ms 31984 KB Ok
86 Correct 640 ms 31700 KB Ok
87 Correct 796 ms 32464 KB Ok
88 Correct 512 ms 31700 KB Ok
89 Correct 766 ms 32208 KB Ok
90 Correct 663 ms 32472 KB Ok
91 Correct 608 ms 32476 KB Ok
92 Correct 708 ms 32208 KB Ok
93 Correct 659 ms 32200 KB Ok
94 Correct 590 ms 31700 KB Ok
95 Correct 273 ms 27084 KB Ok
96 Correct 374 ms 33728 KB Ok
97 Correct 292 ms 32708 KB Ok
98 Correct 193 ms 31680 KB Ok
99 Correct 263 ms 32200 KB Ok
100 Correct 258 ms 32452 KB Ok
101 Correct 296 ms 32956 KB Ok
102 Correct 269 ms 32640 KB Ok
103 Correct 268 ms 32700 KB Ok
104 Correct 324 ms 33984 KB Ok
105 Correct 342 ms 33680 KB Ok
106 Correct 279 ms 33472 KB Ok
107 Correct 297 ms 33264 KB Ok
108 Correct 360 ms 33944 KB Ok
109 Correct 409 ms 33980 KB Ok
110 Execution timed out 2062 ms 63044 KB Time limit exceeded
111 Halted 0 ms 0 KB -