oj.uz

Submission #879407

# Submission time Handle Problem Language Result Execution time Memory
879407 2023-11-27T10:25:07 Z dimashhh Nice sequence (IZhO18_sequence) C++17
61 / 100
 1213 ms 44000 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;
        }
    }
    assert(can(n + m - gcd(n,m) - 1));
    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 64 ms 40148 KB Ok
2 Correct 79 ms 40400 KB Ok
3 Correct 72 ms 33236 KB Ok
4 Correct 67 ms 33612 KB Ok
5 Correct 78 ms 33232 KB Ok
6 Correct 60 ms 34244 KB Ok
7 Correct 64 ms 33236 KB Ok
8 Correct 59 ms 34772 KB Ok
9 Correct 63 ms 33488 KB Ok
10 Correct 63 ms 36044 KB Ok
11 Correct 83 ms 33236 KB Ok
12 Correct 67 ms 33232 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 39632 KB Ok
2 Correct 71 ms 39584 KB Ok
3 Correct 79 ms 39740 KB Ok
4 Correct 69 ms 39632 KB Ok
5 Correct 74 ms 39620 KB Ok
6 Correct 71 ms 40148 KB Ok
7 Correct 98 ms 39892 KB Ok
8 Correct 82 ms 39892 KB Ok
9 Correct 91 ms 40164 KB Ok
10 Correct 75 ms 39876 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40144 KB Ok
2 Correct 71 ms 40144 KB Ok
3 Correct 68 ms 39632 KB Ok
4 Correct 69 ms 40176 KB Ok
5 Correct 68 ms 40148 KB Ok
6 Correct 78 ms 39620 KB Ok
7 Correct 67 ms 40148 KB Ok
8 Correct 77 ms 40144 KB Ok
9 Correct 75 ms 39580 KB Ok
10 Correct 73 ms 39620 KB Ok
11 Correct 68 ms 39624 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 40144 KB Ok
2 Correct 71 ms 40100 KB Ok
3 Correct 74 ms 40148 KB Ok
4 Correct 88 ms 40148 KB Ok
5 Correct 76 ms 40144 KB Ok
6 Incorrect 386 ms 43568 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 64 ms 40148 KB Ok
2 Correct 79 ms 40400 KB Ok
3 Correct 72 ms 33236 KB Ok
4 Correct 67 ms 33612 KB Ok
5 Correct 78 ms 33232 KB Ok
6 Correct 60 ms 34244 KB Ok
7 Correct 64 ms 33236 KB Ok
8 Correct 59 ms 34772 KB Ok
9 Correct 63 ms 33488 KB Ok
10 Correct 63 ms 36044 KB Ok
11 Correct 83 ms 33236 KB Ok
12 Correct 67 ms 33232 KB Ok
13 Correct 36 ms 40144 KB Ok
14 Correct 71 ms 40144 KB Ok
15 Correct 68 ms 39632 KB Ok
16 Correct 69 ms 40176 KB Ok
17 Correct 68 ms 40148 KB Ok
18 Correct 78 ms 39620 KB Ok
19 Correct 67 ms 40148 KB Ok
20 Correct 77 ms 40144 KB Ok
21 Correct 75 ms 39580 KB Ok
22 Correct 73 ms 39620 KB Ok
23 Correct 68 ms 39624 KB Ok
24 Correct 76 ms 32980 KB Ok
25 Correct 84 ms 32976 KB Ok
26 Correct 92 ms 33488 KB Ok
27 Correct 93 ms 33260 KB Ok
28 Correct 89 ms 32980 KB Ok
29 Correct 80 ms 35064 KB Ok
30 Correct 84 ms 33232 KB Ok
31 Correct 89 ms 33036 KB Ok
32 Correct 87 ms 33236 KB Ok
33 Correct 85 ms 32976 KB Ok
34 Correct 117 ms 39620 KB Ok
35 Correct 134 ms 39880 KB Ok
36 Correct 125 ms 39888 KB Ok
37 Correct 120 ms 39892 KB Ok
38 Correct 124 ms 39736 KB Ok
39 Correct 136 ms 39876 KB Ok
40 Correct 126 ms 40136 KB Ok
41 Correct 144 ms 40064 KB Ok
42 Correct 125 ms 39944 KB Ok
43 Correct 120 ms 40128 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40148 KB Ok
2 Correct 79 ms 40400 KB Ok
3 Correct 72 ms 33236 KB Ok
4 Correct 67 ms 33612 KB Ok
5 Correct 78 ms 33232 KB Ok
6 Correct 60 ms 34244 KB Ok
7 Correct 64 ms 33236 KB Ok
8 Correct 59 ms 34772 KB Ok
9 Correct 63 ms 33488 KB Ok
10 Correct 63 ms 36044 KB Ok
11 Correct 83 ms 33236 KB Ok
12 Correct 67 ms 33232 KB Ok
13 Correct 64 ms 39632 KB Ok
14 Correct 71 ms 39584 KB Ok
15 Correct 79 ms 39740 KB Ok
16 Correct 69 ms 39632 KB Ok
17 Correct 74 ms 39620 KB Ok
18 Correct 71 ms 40148 KB Ok
19 Correct 98 ms 39892 KB Ok
20 Correct 82 ms 39892 KB Ok
21 Correct 91 ms 40164 KB Ok
22 Correct 75 ms 39876 KB Ok
23 Correct 36 ms 40144 KB Ok
24 Correct 71 ms 40144 KB Ok
25 Correct 68 ms 39632 KB Ok
26 Correct 69 ms 40176 KB Ok
27 Correct 68 ms 40148 KB Ok
28 Correct 78 ms 39620 KB Ok
29 Correct 67 ms 40148 KB Ok
30 Correct 77 ms 40144 KB Ok
31 Correct 75 ms 39580 KB Ok
32 Correct 73 ms 39620 KB Ok
33 Correct 68 ms 39624 KB Ok
34 Correct 76 ms 32980 KB Ok
35 Correct 84 ms 32976 KB Ok
36 Correct 92 ms 33488 KB Ok
37 Correct 93 ms 33260 KB Ok
38 Correct 89 ms 32980 KB Ok
39 Correct 80 ms 35064 KB Ok
40 Correct 84 ms 33232 KB Ok
41 Correct 89 ms 33036 KB Ok
42 Correct 87 ms 33236 KB Ok
43 Correct 85 ms 32976 KB Ok
44 Correct 117 ms 39620 KB Ok
45 Correct 134 ms 39880 KB Ok
46 Correct 125 ms 39888 KB Ok
47 Correct 120 ms 39892 KB Ok
48 Correct 124 ms 39736 KB Ok
49 Correct 136 ms 39876 KB Ok
50 Correct 126 ms 40136 KB Ok
51 Correct 144 ms 40064 KB Ok
52 Correct 125 ms 39944 KB Ok
53 Correct 120 ms 40128 KB Ok
54 Correct 213 ms 34752 KB Ok
55 Correct 240 ms 35268 KB Ok
56 Correct 247 ms 35140 KB Ok
57 Correct 173 ms 34344 KB Ok
58 Correct 251 ms 35092 KB Ok
59 Correct 222 ms 35016 KB Ok
60 Correct 187 ms 34588 KB Ok
61 Correct 183 ms 34504 KB Ok
62 Correct 262 ms 35268 KB Ok
63 Correct 207 ms 34748 KB Ok
64 Correct 262 ms 35156 KB Ok
65 Correct 220 ms 35076 KB Ok
66 Correct 201 ms 34684 KB Ok
67 Correct 189 ms 34504 KB Ok
68 Correct 259 ms 35056 KB Ok
69 Correct 1213 ms 43344 KB Ok
70 Correct 996 ms 43844 KB Ok
71 Correct 1030 ms 43528 KB Ok
72 Correct 825 ms 43340 KB Ok
73 Correct 947 ms 43656 KB Ok
74 Correct 906 ms 43276 KB Ok
75 Correct 949 ms 43400 KB Ok
76 Correct 808 ms 43536 KB Ok
77 Correct 729 ms 43456 KB Ok
78 Correct 744 ms 43460 KB Ok
79 Correct 814 ms 43940 KB Ok
80 Correct 873 ms 43544 KB Ok
81 Correct 852 ms 44000 KB Ok
82 Correct 936 ms 43492 KB Ok
83 Correct 811 ms 43588 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40148 KB Ok
2 Correct 79 ms 40400 KB Ok
3 Correct 72 ms 33236 KB Ok
4 Correct 67 ms 33612 KB Ok
5 Correct 78 ms 33232 KB Ok
6 Correct 60 ms 34244 KB Ok
7 Correct 64 ms 33236 KB Ok
8 Correct 59 ms 34772 KB Ok
9 Correct 63 ms 33488 KB Ok
10 Correct 63 ms 36044 KB Ok
11 Correct 83 ms 33236 KB Ok
12 Correct 67 ms 33232 KB Ok
13 Correct 64 ms 39632 KB Ok
14 Correct 71 ms 39584 KB Ok
15 Correct 79 ms 39740 KB Ok
16 Correct 69 ms 39632 KB Ok
17 Correct 74 ms 39620 KB Ok
18 Correct 71 ms 40148 KB Ok
19 Correct 98 ms 39892 KB Ok
20 Correct 82 ms 39892 KB Ok
21 Correct 91 ms 40164 KB Ok
22 Correct 75 ms 39876 KB Ok
23 Correct 36 ms 40144 KB Ok
24 Correct 71 ms 40144 KB Ok
25 Correct 68 ms 39632 KB Ok
26 Correct 69 ms 40176 KB Ok
27 Correct 68 ms 40148 KB Ok
28 Correct 78 ms 39620 KB Ok
29 Correct 67 ms 40148 KB Ok
30 Correct 77 ms 40144 KB Ok
31 Correct 75 ms 39580 KB Ok
32 Correct 73 ms 39620 KB Ok
33 Correct 68 ms 39624 KB Ok
34 Correct 67 ms 40144 KB Ok
35 Correct 71 ms 40100 KB Ok
36 Correct 74 ms 40148 KB Ok
37 Correct 88 ms 40148 KB Ok
38 Correct 76 ms 40144 KB Ok
39 Incorrect 386 ms 43568 KB Jury has the better answer : jans = 166803, pans = 149999
40 Halted 0 ms 0 KB -