oj.uz

Submission #879406

# Submission time Handle Problem Language Result Execution time Memory
879406 2023-11-27T10:23:33 Z dimashhh Nice sequence (IZhO18_sequence) C++17
61 / 100
 893 ms 43976 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){
    
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
            // cout << i - m << ' ' << i << '\n';
        }
        if(i - n >= 0){
            // cout << i << ' ' << i - n << '\n';
            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++;
    }
    bool res = ok;
    ok = true;
    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 res;
}
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 40040 KB Ok
2 Correct 69 ms 40148 KB Ok
3 Correct 73 ms 33236 KB Ok
4 Correct 73 ms 33664 KB Ok
5 Correct 97 ms 33216 KB Ok
6 Correct 64 ms 34472 KB Ok
7 Correct 79 ms 33236 KB Ok
8 Correct 63 ms 34772 KB Ok
9 Correct 69 ms 33236 KB Ok
10 Correct 65 ms 36036 KB Ok
11 Correct 72 ms 33068 KB Ok
12 Correct 62 ms 33236 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 39632 KB Ok
2 Correct 70 ms 39664 KB Ok
3 Correct 83 ms 39632 KB Ok
4 Correct 80 ms 39632 KB Ok
5 Correct 98 ms 39592 KB Ok
6 Correct 68 ms 40144 KB Ok
7 Correct 82 ms 40020 KB Ok
8 Correct 72 ms 39888 KB Ok
9 Correct 94 ms 40168 KB Ok
10 Correct 75 ms 39928 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 40176 KB Ok
2 Correct 68 ms 40148 KB Ok
3 Correct 73 ms 39620 KB Ok
4 Correct 86 ms 40148 KB Ok
5 Correct 65 ms 40148 KB Ok
6 Correct 65 ms 39624 KB Ok
7 Correct 73 ms 40148 KB Ok
8 Correct 74 ms 40148 KB Ok
9 Correct 72 ms 39624 KB Ok
10 Correct 69 ms 39632 KB Ok
11 Correct 66 ms 39616 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 40148 KB Ok
2 Correct 71 ms 40144 KB Ok
3 Correct 72 ms 40144 KB Ok
4 Correct 75 ms 40388 KB Ok
5 Correct 77 ms 40400 KB Ok
6 Incorrect 297 ms 42948 KB Jury has the better answer : jans = 166803, pans = 149999
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40040 KB Ok
2 Correct 69 ms 40148 KB Ok
3 Correct 73 ms 33236 KB Ok
4 Correct 73 ms 33664 KB Ok
5 Correct 97 ms 33216 KB Ok
6 Correct 64 ms 34472 KB Ok
7 Correct 79 ms 33236 KB Ok
8 Correct 63 ms 34772 KB Ok
9 Correct 69 ms 33236 KB Ok
10 Correct 65 ms 36036 KB Ok
11 Correct 72 ms 33068 KB Ok
12 Correct 62 ms 33236 KB Ok
13 Correct 38 ms 40176 KB Ok
14 Correct 68 ms 40148 KB Ok
15 Correct 73 ms 39620 KB Ok
16 Correct 86 ms 40148 KB Ok
17 Correct 65 ms 40148 KB Ok
18 Correct 65 ms 39624 KB Ok
19 Correct 73 ms 40148 KB Ok
20 Correct 74 ms 40148 KB Ok
21 Correct 72 ms 39624 KB Ok
22 Correct 69 ms 39632 KB Ok
23 Correct 66 ms 39616 KB Ok
24 Correct 77 ms 32976 KB Ok
25 Correct 96 ms 32980 KB Ok
26 Correct 83 ms 33492 KB Ok
27 Correct 109 ms 33248 KB Ok
28 Correct 81 ms 32980 KB Ok
29 Correct 91 ms 35056 KB Ok
30 Correct 82 ms 33488 KB Ok
31 Correct 82 ms 32976 KB Ok
32 Correct 88 ms 33232 KB Ok
33 Correct 86 ms 32980 KB Ok
34 Correct 140 ms 39708 KB Ok
35 Correct 116 ms 40148 KB Ok
36 Correct 121 ms 39884 KB Ok
37 Correct 162 ms 39960 KB Ok
38 Correct 112 ms 39880 KB Ok
39 Correct 125 ms 39840 KB Ok
40 Correct 159 ms 39900 KB Ok
41 Correct 109 ms 39888 KB Ok
42 Correct 129 ms 39892 KB Ok
43 Correct 133 ms 40144 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40040 KB Ok
2 Correct 69 ms 40148 KB Ok
3 Correct 73 ms 33236 KB Ok
4 Correct 73 ms 33664 KB Ok
5 Correct 97 ms 33216 KB Ok
6 Correct 64 ms 34472 KB Ok
7 Correct 79 ms 33236 KB Ok
8 Correct 63 ms 34772 KB Ok
9 Correct 69 ms 33236 KB Ok
10 Correct 65 ms 36036 KB Ok
11 Correct 72 ms 33068 KB Ok
12 Correct 62 ms 33236 KB Ok
13 Correct 68 ms 39632 KB Ok
14 Correct 70 ms 39664 KB Ok
15 Correct 83 ms 39632 KB Ok
16 Correct 80 ms 39632 KB Ok
17 Correct 98 ms 39592 KB Ok
18 Correct 68 ms 40144 KB Ok
19 Correct 82 ms 40020 KB Ok
20 Correct 72 ms 39888 KB Ok
21 Correct 94 ms 40168 KB Ok
22 Correct 75 ms 39928 KB Ok
23 Correct 38 ms 40176 KB Ok
24 Correct 68 ms 40148 KB Ok
25 Correct 73 ms 39620 KB Ok
26 Correct 86 ms 40148 KB Ok
27 Correct 65 ms 40148 KB Ok
28 Correct 65 ms 39624 KB Ok
29 Correct 73 ms 40148 KB Ok
30 Correct 74 ms 40148 KB Ok
31 Correct 72 ms 39624 KB Ok
32 Correct 69 ms 39632 KB Ok
33 Correct 66 ms 39616 KB Ok
34 Correct 77 ms 32976 KB Ok
35 Correct 96 ms 32980 KB Ok
36 Correct 83 ms 33492 KB Ok
37 Correct 109 ms 33248 KB Ok
38 Correct 81 ms 32980 KB Ok
39 Correct 91 ms 35056 KB Ok
40 Correct 82 ms 33488 KB Ok
41 Correct 82 ms 32976 KB Ok
42 Correct 88 ms 33232 KB Ok
43 Correct 86 ms 32980 KB Ok
44 Correct 140 ms 39708 KB Ok
45 Correct 116 ms 40148 KB Ok
46 Correct 121 ms 39884 KB Ok
47 Correct 162 ms 39960 KB Ok
48 Correct 112 ms 39880 KB Ok
49 Correct 125 ms 39840 KB Ok
50 Correct 159 ms 39900 KB Ok
51 Correct 109 ms 39888 KB Ok
52 Correct 129 ms 39892 KB Ok
53 Correct 133 ms 40144 KB Ok
54 Correct 225 ms 34948 KB Ok
55 Correct 232 ms 35080 KB Ok
56 Correct 238 ms 35252 KB Ok
57 Correct 169 ms 34244 KB Ok
58 Correct 238 ms 35012 KB Ok
59 Correct 226 ms 35012 KB Ok
60 Correct 188 ms 34504 KB Ok
61 Correct 187 ms 34568 KB Ok
62 Correct 255 ms 35268 KB Ok
63 Correct 208 ms 34860 KB Ok
64 Correct 245 ms 35108 KB Ok
65 Correct 251 ms 35012 KB Ok
66 Correct 197 ms 34664 KB Ok
67 Correct 187 ms 34396 KB Ok
68 Correct 220 ms 35028 KB Ok
69 Correct 864 ms 43520 KB Ok
70 Correct 804 ms 43880 KB Ok
71 Correct 734 ms 43528 KB Ok
72 Correct 723 ms 43276 KB Ok
73 Correct 767 ms 43696 KB Ok
74 Correct 741 ms 43532 KB Ok
75 Correct 741 ms 43404 KB Ok
76 Correct 893 ms 43436 KB Ok
77 Correct 804 ms 43244 KB Ok
78 Correct 884 ms 43608 KB Ok
79 Correct 801 ms 43976 KB Ok
80 Correct 716 ms 43528 KB Ok
81 Correct 742 ms 43940 KB Ok
82 Correct 775 ms 43440 KB Ok
83 Correct 755 ms 43588 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40040 KB Ok
2 Correct 69 ms 40148 KB Ok
3 Correct 73 ms 33236 KB Ok
4 Correct 73 ms 33664 KB Ok
5 Correct 97 ms 33216 KB Ok
6 Correct 64 ms 34472 KB Ok
7 Correct 79 ms 33236 KB Ok
8 Correct 63 ms 34772 KB Ok
9 Correct 69 ms 33236 KB Ok
10 Correct 65 ms 36036 KB Ok
11 Correct 72 ms 33068 KB Ok
12 Correct 62 ms 33236 KB Ok
13 Correct 68 ms 39632 KB Ok
14 Correct 70 ms 39664 KB Ok
15 Correct 83 ms 39632 KB Ok
16 Correct 80 ms 39632 KB Ok
17 Correct 98 ms 39592 KB Ok
18 Correct 68 ms 40144 KB Ok
19 Correct 82 ms 40020 KB Ok
20 Correct 72 ms 39888 KB Ok
21 Correct 94 ms 40168 KB Ok
22 Correct 75 ms 39928 KB Ok
23 Correct 38 ms 40176 KB Ok
24 Correct 68 ms 40148 KB Ok
25 Correct 73 ms 39620 KB Ok
26 Correct 86 ms 40148 KB Ok
27 Correct 65 ms 40148 KB Ok
28 Correct 65 ms 39624 KB Ok
29 Correct 73 ms 40148 KB Ok
30 Correct 74 ms 40148 KB Ok
31 Correct 72 ms 39624 KB Ok
32 Correct 69 ms 39632 KB Ok
33 Correct 66 ms 39616 KB Ok
34 Correct 70 ms 40148 KB Ok
35 Correct 71 ms 40144 KB Ok
36 Correct 72 ms 40144 KB Ok
37 Correct 75 ms 40388 KB Ok
38 Correct 77 ms 40400 KB Ok
39 Incorrect 297 ms 42948 KB Jury has the better answer : jans = 166803, pans = 149999
40 Halted 0 ms 0 KB -