oj.uz

Submission #879425

# Submission time Handle Problem Language Result Execution time Memory
879425 2023-11-27T10:53:32 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 911 ms 49192 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, MOD = 998244353;
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = false;
void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(used[to] == 1){
            ok = false;
        }
        if(!used[to]){
            dfs(to);
        }
    }
    used[v] = 2;
    ord.push_back(v);
}
bool can(int len){
    ok = 1;
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
        }
        if(i - n >= 0){
            g[i].push_back(i - n);
        }
    }
    for(int i = 0;i <= len;i++){
        if(!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(auto i:ord){
        pref[i] = timer++;
    }
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
    return ok;
}
void test(){
    cin >> n >> m;
    int l = 0,r = 3e5;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(can(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    can(l);
    cout << l << '\n';
    for(int i = 1;i <= l;i++){
        cout << pref[i] - pref[i - 1] << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40140 KB Ok
2 Correct 67 ms 40144 KB Ok
3 Correct 67 ms 33236 KB Ok
4 Correct 68 ms 33476 KB Ok
5 Correct 76 ms 33232 KB Ok
6 Correct 63 ms 34252 KB Ok
7 Correct 67 ms 33236 KB Ok
8 Correct 78 ms 34824 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 65 ms 36040 KB Ok
11 Correct 69 ms 33232 KB Ok
12 Correct 60 ms 33232 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 39620 KB Ok
2 Correct 76 ms 39888 KB Ok
3 Correct 77 ms 39624 KB Ok
4 Correct 76 ms 39632 KB Ok
5 Correct 71 ms 39628 KB Ok
6 Correct 67 ms 40148 KB Ok
7 Correct 79 ms 39892 KB Ok
8 Correct 71 ms 39888 KB Ok
9 Correct 108 ms 40156 KB Ok
10 Correct 74 ms 39880 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40144 KB Ok
2 Correct 65 ms 40148 KB Ok
3 Correct 66 ms 39580 KB Ok
4 Correct 67 ms 40144 KB Ok
5 Correct 67 ms 40040 KB Ok
6 Correct 67 ms 39632 KB Ok
7 Correct 70 ms 40396 KB Ok
8 Correct 66 ms 40144 KB Ok
9 Correct 69 ms 39564 KB Ok
10 Correct 66 ms 39628 KB Ok
11 Correct 64 ms 39600 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 40148 KB Ok
2 Correct 74 ms 40136 KB Ok
3 Correct 75 ms 40136 KB Ok
4 Correct 73 ms 40148 KB Ok
5 Correct 77 ms 40148 KB Ok
6 Correct 383 ms 45800 KB Ok
7 Correct 280 ms 46564 KB Ok
8 Correct 587 ms 48476 KB Ok
9 Correct 395 ms 48600 KB Ok
10 Correct 223 ms 42152 KB Ok
11 Correct 419 ms 49192 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40140 KB Ok
2 Correct 67 ms 40144 KB Ok
3 Correct 67 ms 33236 KB Ok
4 Correct 68 ms 33476 KB Ok
5 Correct 76 ms 33232 KB Ok
6 Correct 63 ms 34252 KB Ok
7 Correct 67 ms 33236 KB Ok
8 Correct 78 ms 34824 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 65 ms 36040 KB Ok
11 Correct 69 ms 33232 KB Ok
12 Correct 60 ms 33232 KB Ok
13 Correct 39 ms 40144 KB Ok
14 Correct 65 ms 40148 KB Ok
15 Correct 66 ms 39580 KB Ok
16 Correct 67 ms 40144 KB Ok
17 Correct 67 ms 40040 KB Ok
18 Correct 67 ms 39632 KB Ok
19 Correct 70 ms 40396 KB Ok
20 Correct 66 ms 40144 KB Ok
21 Correct 69 ms 39564 KB Ok
22 Correct 66 ms 39628 KB Ok
23 Correct 64 ms 39600 KB Ok
24 Correct 79 ms 32976 KB Ok
25 Correct 82 ms 32980 KB Ok
26 Correct 98 ms 33492 KB Ok
27 Correct 85 ms 33240 KB Ok
28 Correct 87 ms 32976 KB Ok
29 Correct 93 ms 35048 KB Ok
30 Correct 81 ms 33232 KB Ok
31 Correct 84 ms 32976 KB Ok
32 Correct 91 ms 33236 KB Ok
33 Correct 83 ms 33024 KB Ok
34 Correct 128 ms 39752 KB Ok
35 Correct 114 ms 39924 KB Ok
36 Correct 146 ms 39928 KB Ok
37 Correct 120 ms 40120 KB Ok
38 Correct 110 ms 39880 KB Ok
39 Correct 133 ms 39880 KB Ok
40 Correct 136 ms 39984 KB Ok
41 Correct 114 ms 39892 KB Ok
42 Correct 135 ms 39892 KB Ok
43 Correct 132 ms 40144 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40140 KB Ok
2 Correct 67 ms 40144 KB Ok
3 Correct 67 ms 33236 KB Ok
4 Correct 68 ms 33476 KB Ok
5 Correct 76 ms 33232 KB Ok
6 Correct 63 ms 34252 KB Ok
7 Correct 67 ms 33236 KB Ok
8 Correct 78 ms 34824 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 65 ms 36040 KB Ok
11 Correct 69 ms 33232 KB Ok
12 Correct 60 ms 33232 KB Ok
13 Correct 65 ms 39620 KB Ok
14 Correct 76 ms 39888 KB Ok
15 Correct 77 ms 39624 KB Ok
16 Correct 76 ms 39632 KB Ok
17 Correct 71 ms 39628 KB Ok
18 Correct 67 ms 40148 KB Ok
19 Correct 79 ms 39892 KB Ok
20 Correct 71 ms 39888 KB Ok
21 Correct 108 ms 40156 KB Ok
22 Correct 74 ms 39880 KB Ok
23 Correct 39 ms 40144 KB Ok
24 Correct 65 ms 40148 KB Ok
25 Correct 66 ms 39580 KB Ok
26 Correct 67 ms 40144 KB Ok
27 Correct 67 ms 40040 KB Ok
28 Correct 67 ms 39632 KB Ok
29 Correct 70 ms 40396 KB Ok
30 Correct 66 ms 40144 KB Ok
31 Correct 69 ms 39564 KB Ok
32 Correct 66 ms 39628 KB Ok
33 Correct 64 ms 39600 KB Ok
34 Correct 79 ms 32976 KB Ok
35 Correct 82 ms 32980 KB Ok
36 Correct 98 ms 33492 KB Ok
37 Correct 85 ms 33240 KB Ok
38 Correct 87 ms 32976 KB Ok
39 Correct 93 ms 35048 KB Ok
40 Correct 81 ms 33232 KB Ok
41 Correct 84 ms 32976 KB Ok
42 Correct 91 ms 33236 KB Ok
43 Correct 83 ms 33024 KB Ok
44 Correct 128 ms 39752 KB Ok
45 Correct 114 ms 39924 KB Ok
46 Correct 146 ms 39928 KB Ok
47 Correct 120 ms 40120 KB Ok
48 Correct 110 ms 39880 KB Ok
49 Correct 133 ms 39880 KB Ok
50 Correct 136 ms 39984 KB Ok
51 Correct 114 ms 39892 KB Ok
52 Correct 135 ms 39892 KB Ok
53 Correct 132 ms 40144 KB Ok
54 Correct 224 ms 34832 KB Ok
55 Correct 235 ms 35248 KB Ok
56 Correct 249 ms 35208 KB Ok
57 Correct 172 ms 34372 KB Ok
58 Correct 245 ms 35276 KB Ok
59 Correct 235 ms 34920 KB Ok
60 Correct 189 ms 34512 KB Ok
61 Correct 204 ms 34480 KB Ok
62 Correct 252 ms 35268 KB Ok
63 Correct 222 ms 34860 KB Ok
64 Correct 273 ms 35100 KB Ok
65 Correct 234 ms 35116 KB Ok
66 Correct 193 ms 34840 KB Ok
67 Correct 204 ms 34712 KB Ok
68 Correct 240 ms 35008 KB Ok
69 Correct 911 ms 43788 KB Ok
70 Correct 726 ms 43716 KB Ok
71 Correct 771 ms 43460 KB Ok
72 Correct 730 ms 43268 KB Ok
73 Correct 840 ms 43772 KB Ok
74 Correct 734 ms 43408 KB Ok
75 Correct 791 ms 43444 KB Ok
76 Correct 804 ms 43700 KB Ok
77 Correct 734 ms 43428 KB Ok
78 Correct 790 ms 43420 KB Ok
79 Correct 734 ms 43720 KB Ok
80 Correct 733 ms 43280 KB Ok
81 Correct 740 ms 43768 KB Ok
82 Correct 747 ms 43456 KB Ok
83 Correct 910 ms 43492 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40140 KB Ok
2 Correct 67 ms 40144 KB Ok
3 Correct 67 ms 33236 KB Ok
4 Correct 68 ms 33476 KB Ok
5 Correct 76 ms 33232 KB Ok
6 Correct 63 ms 34252 KB Ok
7 Correct 67 ms 33236 KB Ok
8 Correct 78 ms 34824 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 65 ms 36040 KB Ok
11 Correct 69 ms 33232 KB Ok
12 Correct 60 ms 33232 KB Ok
13 Correct 65 ms 39620 KB Ok
14 Correct 76 ms 39888 KB Ok
15 Correct 77 ms 39624 KB Ok
16 Correct 76 ms 39632 KB Ok
17 Correct 71 ms 39628 KB Ok
18 Correct 67 ms 40148 KB Ok
19 Correct 79 ms 39892 KB Ok
20 Correct 71 ms 39888 KB Ok
21 Correct 108 ms 40156 KB Ok
22 Correct 74 ms 39880 KB Ok
23 Correct 39 ms 40144 KB Ok
24 Correct 65 ms 40148 KB Ok
25 Correct 66 ms 39580 KB Ok
26 Correct 67 ms 40144 KB Ok
27 Correct 67 ms 40040 KB Ok
28 Correct 67 ms 39632 KB Ok
29 Correct 70 ms 40396 KB Ok
30 Correct 66 ms 40144 KB Ok
31 Correct 69 ms 39564 KB Ok
32 Correct 66 ms 39628 KB Ok
33 Correct 64 ms 39600 KB Ok
34 Correct 73 ms 40148 KB Ok
35 Correct 74 ms 40136 KB Ok
36 Correct 75 ms 40136 KB Ok
37 Correct 73 ms 40148 KB Ok
38 Correct 77 ms 40148 KB Ok
39 Correct 383 ms 45800 KB Ok
40 Correct 280 ms 46564 KB Ok
41 Correct 587 ms 48476 KB Ok
42 Correct 395 ms 48600 KB Ok
43 Correct 223 ms 42152 KB Ok
44 Correct 419 ms 49192 KB Ok
45 Correct 79 ms 32976 KB Ok
46 Correct 82 ms 32980 KB Ok
47 Correct 98 ms 33492 KB Ok
48 Correct 85 ms 33240 KB Ok
49 Correct 87 ms 32976 KB Ok
50 Correct 93 ms 35048 KB Ok
51 Correct 81 ms 33232 KB Ok
52 Correct 84 ms 32976 KB Ok
53 Correct 91 ms 33236 KB Ok
54 Correct 83 ms 33024 KB Ok
55 Correct 128 ms 39752 KB Ok
56 Correct 114 ms 39924 KB Ok
57 Correct 146 ms 39928 KB Ok
58 Correct 120 ms 40120 KB Ok
59 Correct 110 ms 39880 KB Ok
60 Correct 133 ms 39880 KB Ok
61 Correct 136 ms 39984 KB Ok
62 Correct 114 ms 39892 KB Ok
63 Correct 135 ms 39892 KB Ok
64 Correct 132 ms 40144 KB Ok
65 Correct 224 ms 34832 KB Ok
66 Correct 235 ms 35248 KB Ok
67 Correct 249 ms 35208 KB Ok
68 Correct 172 ms 34372 KB Ok
69 Correct 245 ms 35276 KB Ok
70 Correct 235 ms 34920 KB Ok
71 Correct 189 ms 34512 KB Ok
72 Correct 204 ms 34480 KB Ok
73 Correct 252 ms 35268 KB Ok
74 Correct 222 ms 34860 KB Ok
75 Correct 273 ms 35100 KB Ok
76 Correct 234 ms 35116 KB Ok
77 Correct 193 ms 34840 KB Ok
78 Correct 204 ms 34712 KB Ok
79 Correct 240 ms 35008 KB Ok
80 Correct 911 ms 43788 KB Ok
81 Correct 726 ms 43716 KB Ok
82 Correct 771 ms 43460 KB Ok
83 Correct 730 ms 43268 KB Ok
84 Correct 840 ms 43772 KB Ok
85 Correct 734 ms 43408 KB Ok
86 Correct 791 ms 43444 KB Ok
87 Correct 804 ms 43700 KB Ok
88 Correct 734 ms 43428 KB Ok
89 Correct 790 ms 43420 KB Ok
90 Correct 734 ms 43720 KB Ok
91 Correct 733 ms 43280 KB Ok
92 Correct 740 ms 43768 KB Ok
93 Correct 747 ms 43456 KB Ok
94 Correct 910 ms 43492 KB Ok
95 Correct 501 ms 42136 KB Ok
96 Incorrect 675 ms 45244 KB Jury has the better answer : jans = 311847, pans = 299999
97 Halted 0 ms 0 KB -