oj.uz

Submission #879409

# Submission time Handle Problem Language Result Execution time Memory
879409 2023-11-27T10:26:03 Z dimashhh Nice sequence (IZhO18_sequence) C++17
61 / 100
 2000 ms 43744 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;
        }
    }
    
    for(int i = l;i <= n + m - gcd(n,m) - 1;i++){
        assert(can(i));
    }
    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 68 ms 40148 KB Ok
2 Correct 67 ms 40148 KB Ok
3 Correct 68 ms 33236 KB Ok
4 Correct 65 ms 33672 KB Ok
5 Correct 78 ms 33236 KB Ok
6 Correct 64 ms 34716 KB Ok
7 Correct 65 ms 33232 KB Ok
8 Correct 67 ms 34772 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 66 ms 35996 KB Ok
11 Correct 67 ms 33236 KB Ok
12 Correct 71 ms 33236 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 39620 KB Ok
2 Correct 70 ms 39624 KB Ok
3 Correct 68 ms 39632 KB Ok
4 Correct 69 ms 39620 KB Ok
5 Correct 81 ms 39580 KB Ok
6 Correct 68 ms 40144 KB Ok
7 Correct 82 ms 39892 KB Ok
8 Correct 72 ms 39880 KB Ok
9 Correct 85 ms 40144 KB Ok
10 Correct 74 ms 39804 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 40148 KB Ok
2 Correct 67 ms 40144 KB Ok
3 Correct 65 ms 39632 KB Ok
4 Correct 75 ms 40148 KB Ok
5 Correct 65 ms 40148 KB Ok
6 Correct 73 ms 39628 KB Ok
7 Correct 68 ms 40112 KB Ok
8 Correct 75 ms 40144 KB Ok
9 Correct 67 ms 39624 KB Ok
10 Correct 67 ms 39620 KB Ok
11 Correct 71 ms 39624 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 40144 KB Ok
2 Correct 75 ms 40148 KB Ok
3 Correct 71 ms 40144 KB Ok
4 Correct 70 ms 40144 KB Ok
5 Correct 76 ms 40148 KB Ok
6 Execution timed out 2045 ms 35852 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 40148 KB Ok
2 Correct 67 ms 40148 KB Ok
3 Correct 68 ms 33236 KB Ok
4 Correct 65 ms 33672 KB Ok
5 Correct 78 ms 33236 KB Ok
6 Correct 64 ms 34716 KB Ok
7 Correct 65 ms 33232 KB Ok
8 Correct 67 ms 34772 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 66 ms 35996 KB Ok
11 Correct 67 ms 33236 KB Ok
12 Correct 71 ms 33236 KB Ok
13 Correct 39 ms 40148 KB Ok
14 Correct 67 ms 40144 KB Ok
15 Correct 65 ms 39632 KB Ok
16 Correct 75 ms 40148 KB Ok
17 Correct 65 ms 40148 KB Ok
18 Correct 73 ms 39628 KB Ok
19 Correct 68 ms 40112 KB Ok
20 Correct 75 ms 40144 KB Ok
21 Correct 67 ms 39624 KB Ok
22 Correct 67 ms 39620 KB Ok
23 Correct 71 ms 39624 KB Ok
24 Correct 83 ms 32980 KB Ok
25 Correct 87 ms 32980 KB Ok
26 Correct 81 ms 33488 KB Ok
27 Correct 86 ms 33484 KB Ok
28 Correct 88 ms 32976 KB Ok
29 Correct 77 ms 35016 KB Ok
30 Correct 81 ms 33488 KB Ok
31 Correct 82 ms 32980 KB Ok
32 Correct 89 ms 33232 KB Ok
33 Correct 84 ms 33236 KB Ok
34 Correct 118 ms 39624 KB Ok
35 Correct 111 ms 39892 KB Ok
36 Correct 122 ms 39892 KB Ok
37 Correct 124 ms 40396 KB Ok
38 Correct 111 ms 39876 KB Ok
39 Correct 130 ms 39880 KB Ok
40 Correct 116 ms 39996 KB Ok
41 Correct 111 ms 39892 KB Ok
42 Correct 123 ms 39888 KB Ok
43 Correct 117 ms 40148 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 40148 KB Ok
2 Correct 67 ms 40148 KB Ok
3 Correct 68 ms 33236 KB Ok
4 Correct 65 ms 33672 KB Ok
5 Correct 78 ms 33236 KB Ok
6 Correct 64 ms 34716 KB Ok
7 Correct 65 ms 33232 KB Ok
8 Correct 67 ms 34772 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 66 ms 35996 KB Ok
11 Correct 67 ms 33236 KB Ok
12 Correct 71 ms 33236 KB Ok
13 Correct 64 ms 39620 KB Ok
14 Correct 70 ms 39624 KB Ok
15 Correct 68 ms 39632 KB Ok
16 Correct 69 ms 39620 KB Ok
17 Correct 81 ms 39580 KB Ok
18 Correct 68 ms 40144 KB Ok
19 Correct 82 ms 39892 KB Ok
20 Correct 72 ms 39880 KB Ok
21 Correct 85 ms 40144 KB Ok
22 Correct 74 ms 39804 KB Ok
23 Correct 39 ms 40148 KB Ok
24 Correct 67 ms 40144 KB Ok
25 Correct 65 ms 39632 KB Ok
26 Correct 75 ms 40148 KB Ok
27 Correct 65 ms 40148 KB Ok
28 Correct 73 ms 39628 KB Ok
29 Correct 68 ms 40112 KB Ok
30 Correct 75 ms 40144 KB Ok
31 Correct 67 ms 39624 KB Ok
32 Correct 67 ms 39620 KB Ok
33 Correct 71 ms 39624 KB Ok
34 Correct 83 ms 32980 KB Ok
35 Correct 87 ms 32980 KB Ok
36 Correct 81 ms 33488 KB Ok
37 Correct 86 ms 33484 KB Ok
38 Correct 88 ms 32976 KB Ok
39 Correct 77 ms 35016 KB Ok
40 Correct 81 ms 33488 KB Ok
41 Correct 82 ms 32980 KB Ok
42 Correct 89 ms 33232 KB Ok
43 Correct 84 ms 33236 KB Ok
44 Correct 118 ms 39624 KB Ok
45 Correct 111 ms 39892 KB Ok
46 Correct 122 ms 39892 KB Ok
47 Correct 124 ms 40396 KB Ok
48 Correct 111 ms 39876 KB Ok
49 Correct 130 ms 39880 KB Ok
50 Correct 116 ms 39996 KB Ok
51 Correct 111 ms 39892 KB Ok
52 Correct 123 ms 39888 KB Ok
53 Correct 117 ms 40148 KB Ok
54 Correct 217 ms 34984 KB Ok
55 Correct 231 ms 35268 KB Ok
56 Correct 247 ms 34996 KB Ok
57 Correct 176 ms 34248 KB Ok
58 Correct 227 ms 35108 KB Ok
59 Correct 225 ms 34916 KB Ok
60 Correct 188 ms 34596 KB Ok
61 Correct 182 ms 34496 KB Ok
62 Correct 253 ms 35268 KB Ok
63 Correct 209 ms 34908 KB Ok
64 Correct 254 ms 35140 KB Ok
65 Correct 231 ms 35268 KB Ok
66 Correct 193 ms 34760 KB Ok
67 Correct 183 ms 34380 KB Ok
68 Correct 218 ms 34928 KB Ok
69 Correct 770 ms 43532 KB Ok
70 Correct 792 ms 43744 KB Ok
71 Correct 748 ms 43716 KB Ok
72 Correct 707 ms 43208 KB Ok
73 Correct 773 ms 43708 KB Ok
74 Correct 853 ms 43512 KB Ok
75 Correct 752 ms 43496 KB Ok
76 Correct 767 ms 43552 KB Ok
77 Correct 711 ms 43232 KB Ok
78 Correct 734 ms 43456 KB Ok
79 Correct 925 ms 43640 KB Ok
80 Correct 724 ms 43460 KB Ok
81 Correct 874 ms 43716 KB Ok
82 Correct 775 ms 43716 KB Ok
83 Correct 754 ms 43464 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 40148 KB Ok
2 Correct 67 ms 40148 KB Ok
3 Correct 68 ms 33236 KB Ok
4 Correct 65 ms 33672 KB Ok
5 Correct 78 ms 33236 KB Ok
6 Correct 64 ms 34716 KB Ok
7 Correct 65 ms 33232 KB Ok
8 Correct 67 ms 34772 KB Ok
9 Correct 63 ms 33236 KB Ok
10 Correct 66 ms 35996 KB Ok
11 Correct 67 ms 33236 KB Ok
12 Correct 71 ms 33236 KB Ok
13 Correct 64 ms 39620 KB Ok
14 Correct 70 ms 39624 KB Ok
15 Correct 68 ms 39632 KB Ok
16 Correct 69 ms 39620 KB Ok
17 Correct 81 ms 39580 KB Ok
18 Correct 68 ms 40144 KB Ok
19 Correct 82 ms 39892 KB Ok
20 Correct 72 ms 39880 KB Ok
21 Correct 85 ms 40144 KB Ok
22 Correct 74 ms 39804 KB Ok
23 Correct 39 ms 40148 KB Ok
24 Correct 67 ms 40144 KB Ok
25 Correct 65 ms 39632 KB Ok
26 Correct 75 ms 40148 KB Ok
27 Correct 65 ms 40148 KB Ok
28 Correct 73 ms 39628 KB Ok
29 Correct 68 ms 40112 KB Ok
30 Correct 75 ms 40144 KB Ok
31 Correct 67 ms 39624 KB Ok
32 Correct 67 ms 39620 KB Ok
33 Correct 71 ms 39624 KB Ok
34 Correct 66 ms 40144 KB Ok
35 Correct 75 ms 40148 KB Ok
36 Correct 71 ms 40144 KB Ok
37 Correct 70 ms 40144 KB Ok
38 Correct 76 ms 40148 KB Ok
39 Execution timed out 2045 ms 35852 KB Time limit exceeded
40 Halted 0 ms 0 KB -