oj.uz

Submission #879424

# Submission time Handle Problem Language Result Execution time Memory
879424 2023-11-27T10:49:28 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 58372 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 = 4e5;
    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 107 ms 43952 KB Ok
2 Correct 99 ms 43984 KB Ok
3 Correct 107 ms 34968 KB Ok
4 Correct 97 ms 35780 KB Ok
5 Correct 115 ms 35024 KB Ok
6 Correct 85 ms 36832 KB Ok
7 Correct 93 ms 34772 KB Ok
8 Correct 92 ms 37076 KB Ok
9 Correct 88 ms 35008 KB Ok
10 Correct 90 ms 39100 KB Ok
11 Correct 101 ms 34952 KB Ok
12 Correct 91 ms 34768 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 43728 KB Ok
2 Correct 96 ms 43716 KB Ok
3 Correct 117 ms 43720 KB Ok
4 Correct 103 ms 43696 KB Ok
5 Correct 109 ms 43820 KB Ok
6 Correct 96 ms 44068 KB Ok
7 Correct 112 ms 43968 KB Ok
8 Correct 99 ms 43988 KB Ok
9 Correct 135 ms 44276 KB Ok
10 Correct 112 ms 44128 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 43988 KB Ok
2 Correct 95 ms 43988 KB Ok
3 Correct 94 ms 43672 KB Ok
4 Correct 97 ms 43988 KB Ok
5 Correct 94 ms 43980 KB Ok
6 Correct 93 ms 43724 KB Ok
7 Correct 106 ms 44104 KB Ok
8 Correct 93 ms 43988 KB Ok
9 Correct 94 ms 43788 KB Ok
10 Correct 97 ms 43716 KB Ok
11 Correct 99 ms 43716 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 43984 KB Ok
2 Correct 104 ms 43952 KB Ok
3 Correct 110 ms 43968 KB Ok
4 Correct 107 ms 43976 KB Ok
5 Correct 118 ms 44140 KB Ok
6 Correct 362 ms 47300 KB Ok
7 Correct 307 ms 45688 KB Ok
8 Correct 587 ms 48600 KB Ok
9 Correct 430 ms 49348 KB Ok
10 Correct 275 ms 46752 KB Ok
11 Correct 411 ms 48492 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 43952 KB Ok
2 Correct 99 ms 43984 KB Ok
3 Correct 107 ms 34968 KB Ok
4 Correct 97 ms 35780 KB Ok
5 Correct 115 ms 35024 KB Ok
6 Correct 85 ms 36832 KB Ok
7 Correct 93 ms 34772 KB Ok
8 Correct 92 ms 37076 KB Ok
9 Correct 88 ms 35008 KB Ok
10 Correct 90 ms 39100 KB Ok
11 Correct 101 ms 34952 KB Ok
12 Correct 91 ms 34768 KB Ok
13 Correct 43 ms 43988 KB Ok
14 Correct 95 ms 43988 KB Ok
15 Correct 94 ms 43672 KB Ok
16 Correct 97 ms 43988 KB Ok
17 Correct 94 ms 43980 KB Ok
18 Correct 93 ms 43724 KB Ok
19 Correct 106 ms 44104 KB Ok
20 Correct 93 ms 43988 KB Ok
21 Correct 94 ms 43788 KB Ok
22 Correct 97 ms 43716 KB Ok
23 Correct 99 ms 43716 KB Ok
24 Correct 119 ms 34620 KB Ok
25 Correct 114 ms 34688 KB Ok
26 Correct 110 ms 35284 KB Ok
27 Correct 127 ms 35168 KB Ok
28 Correct 133 ms 34676 KB Ok
29 Correct 111 ms 37564 KB Ok
30 Correct 114 ms 35028 KB Ok
31 Correct 150 ms 35052 KB Ok
32 Correct 120 ms 34836 KB Ok
33 Correct 139 ms 35012 KB Ok
34 Correct 205 ms 43888 KB Ok
35 Correct 185 ms 44000 KB Ok
36 Correct 183 ms 43952 KB Ok
37 Correct 175 ms 43988 KB Ok
38 Correct 185 ms 43928 KB Ok
39 Correct 235 ms 43972 KB Ok
40 Correct 232 ms 43912 KB Ok
41 Correct 173 ms 43980 KB Ok
42 Correct 209 ms 43976 KB Ok
43 Correct 178 ms 43980 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 43952 KB Ok
2 Correct 99 ms 43984 KB Ok
3 Correct 107 ms 34968 KB Ok
4 Correct 97 ms 35780 KB Ok
5 Correct 115 ms 35024 KB Ok
6 Correct 85 ms 36832 KB Ok
7 Correct 93 ms 34772 KB Ok
8 Correct 92 ms 37076 KB Ok
9 Correct 88 ms 35008 KB Ok
10 Correct 90 ms 39100 KB Ok
11 Correct 101 ms 34952 KB Ok
12 Correct 91 ms 34768 KB Ok
13 Correct 90 ms 43728 KB Ok
14 Correct 96 ms 43716 KB Ok
15 Correct 117 ms 43720 KB Ok
16 Correct 103 ms 43696 KB Ok
17 Correct 109 ms 43820 KB Ok
18 Correct 96 ms 44068 KB Ok
19 Correct 112 ms 43968 KB Ok
20 Correct 99 ms 43988 KB Ok
21 Correct 135 ms 44276 KB Ok
22 Correct 112 ms 44128 KB Ok
23 Correct 43 ms 43988 KB Ok
24 Correct 95 ms 43988 KB Ok
25 Correct 94 ms 43672 KB Ok
26 Correct 97 ms 43988 KB Ok
27 Correct 94 ms 43980 KB Ok
28 Correct 93 ms 43724 KB Ok
29 Correct 106 ms 44104 KB Ok
30 Correct 93 ms 43988 KB Ok
31 Correct 94 ms 43788 KB Ok
32 Correct 97 ms 43716 KB Ok
33 Correct 99 ms 43716 KB Ok
34 Correct 119 ms 34620 KB Ok
35 Correct 114 ms 34688 KB Ok
36 Correct 110 ms 35284 KB Ok
37 Correct 127 ms 35168 KB Ok
38 Correct 133 ms 34676 KB Ok
39 Correct 111 ms 37564 KB Ok
40 Correct 114 ms 35028 KB Ok
41 Correct 150 ms 35052 KB Ok
42 Correct 120 ms 34836 KB Ok
43 Correct 139 ms 35012 KB Ok
44 Correct 205 ms 43888 KB Ok
45 Correct 185 ms 44000 KB Ok
46 Correct 183 ms 43952 KB Ok
47 Correct 175 ms 43988 KB Ok
48 Correct 185 ms 43928 KB Ok
49 Correct 235 ms 43972 KB Ok
50 Correct 232 ms 43912 KB Ok
51 Correct 173 ms 43980 KB Ok
52 Correct 209 ms 43976 KB Ok
53 Correct 178 ms 43980 KB Ok
54 Correct 227 ms 36548 KB Ok
55 Correct 258 ms 37060 KB Ok
56 Correct 251 ms 36948 KB Ok
57 Correct 213 ms 36152 KB Ok
58 Correct 248 ms 36744 KB Ok
59 Correct 230 ms 36728 KB Ok
60 Correct 201 ms 36284 KB Ok
61 Correct 195 ms 36332 KB Ok
62 Correct 276 ms 37064 KB Ok
63 Correct 225 ms 36628 KB Ok
64 Correct 271 ms 37060 KB Ok
65 Correct 257 ms 36688 KB Ok
66 Correct 207 ms 36400 KB Ok
67 Correct 202 ms 36544 KB Ok
68 Correct 238 ms 36804 KB Ok
69 Correct 876 ms 49844 KB Ok
70 Correct 777 ms 50372 KB Ok
71 Correct 770 ms 49984 KB Ok
72 Correct 706 ms 49804 KB Ok
73 Correct 787 ms 50252 KB Ok
74 Correct 847 ms 49856 KB Ok
75 Correct 791 ms 49808 KB Ok
76 Correct 758 ms 50116 KB Ok
77 Correct 775 ms 49944 KB Ok
78 Correct 764 ms 49896 KB Ok
79 Correct 767 ms 50372 KB Ok
80 Correct 762 ms 49832 KB Ok
81 Correct 689 ms 50120 KB Ok
82 Correct 732 ms 49900 KB Ok
83 Correct 772 ms 49864 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 43952 KB Ok
2 Correct 99 ms 43984 KB Ok
3 Correct 107 ms 34968 KB Ok
4 Correct 97 ms 35780 KB Ok
5 Correct 115 ms 35024 KB Ok
6 Correct 85 ms 36832 KB Ok
7 Correct 93 ms 34772 KB Ok
8 Correct 92 ms 37076 KB Ok
9 Correct 88 ms 35008 KB Ok
10 Correct 90 ms 39100 KB Ok
11 Correct 101 ms 34952 KB Ok
12 Correct 91 ms 34768 KB Ok
13 Correct 90 ms 43728 KB Ok
14 Correct 96 ms 43716 KB Ok
15 Correct 117 ms 43720 KB Ok
16 Correct 103 ms 43696 KB Ok
17 Correct 109 ms 43820 KB Ok
18 Correct 96 ms 44068 KB Ok
19 Correct 112 ms 43968 KB Ok
20 Correct 99 ms 43988 KB Ok
21 Correct 135 ms 44276 KB Ok
22 Correct 112 ms 44128 KB Ok
23 Correct 43 ms 43988 KB Ok
24 Correct 95 ms 43988 KB Ok
25 Correct 94 ms 43672 KB Ok
26 Correct 97 ms 43988 KB Ok
27 Correct 94 ms 43980 KB Ok
28 Correct 93 ms 43724 KB Ok
29 Correct 106 ms 44104 KB Ok
30 Correct 93 ms 43988 KB Ok
31 Correct 94 ms 43788 KB Ok
32 Correct 97 ms 43716 KB Ok
33 Correct 99 ms 43716 KB Ok
34 Correct 102 ms 43984 KB Ok
35 Correct 104 ms 43952 KB Ok
36 Correct 110 ms 43968 KB Ok
37 Correct 107 ms 43976 KB Ok
38 Correct 118 ms 44140 KB Ok
39 Correct 362 ms 47300 KB Ok
40 Correct 307 ms 45688 KB Ok
41 Correct 587 ms 48600 KB Ok
42 Correct 430 ms 49348 KB Ok
43 Correct 275 ms 46752 KB Ok
44 Correct 411 ms 48492 KB Ok
45 Correct 119 ms 34620 KB Ok
46 Correct 114 ms 34688 KB Ok
47 Correct 110 ms 35284 KB Ok
48 Correct 127 ms 35168 KB Ok
49 Correct 133 ms 34676 KB Ok
50 Correct 111 ms 37564 KB Ok
51 Correct 114 ms 35028 KB Ok
52 Correct 150 ms 35052 KB Ok
53 Correct 120 ms 34836 KB Ok
54 Correct 139 ms 35012 KB Ok
55 Correct 205 ms 43888 KB Ok
56 Correct 185 ms 44000 KB Ok
57 Correct 183 ms 43952 KB Ok
58 Correct 175 ms 43988 KB Ok
59 Correct 185 ms 43928 KB Ok
60 Correct 235 ms 43972 KB Ok
61 Correct 232 ms 43912 KB Ok
62 Correct 173 ms 43980 KB Ok
63 Correct 209 ms 43976 KB Ok
64 Correct 178 ms 43980 KB Ok
65 Correct 227 ms 36548 KB Ok
66 Correct 258 ms 37060 KB Ok
67 Correct 251 ms 36948 KB Ok
68 Correct 213 ms 36152 KB Ok
69 Correct 248 ms 36744 KB Ok
70 Correct 230 ms 36728 KB Ok
71 Correct 201 ms 36284 KB Ok
72 Correct 195 ms 36332 KB Ok
73 Correct 276 ms 37064 KB Ok
74 Correct 225 ms 36628 KB Ok
75 Correct 271 ms 37060 KB Ok
76 Correct 257 ms 36688 KB Ok
77 Correct 207 ms 36400 KB Ok
78 Correct 202 ms 36544 KB Ok
79 Correct 238 ms 36804 KB Ok
80 Correct 876 ms 49844 KB Ok
81 Correct 777 ms 50372 KB Ok
82 Correct 770 ms 49984 KB Ok
83 Correct 706 ms 49804 KB Ok
84 Correct 787 ms 50252 KB Ok
85 Correct 847 ms 49856 KB Ok
86 Correct 791 ms 49808 KB Ok
87 Correct 758 ms 50116 KB Ok
88 Correct 775 ms 49944 KB Ok
89 Correct 764 ms 49896 KB Ok
90 Correct 767 ms 50372 KB Ok
91 Correct 762 ms 49832 KB Ok
92 Correct 689 ms 50120 KB Ok
93 Correct 732 ms 49900 KB Ok
94 Correct 772 ms 49864 KB Ok
95 Correct 550 ms 43456 KB Ok
96 Correct 854 ms 48980 KB Ok
97 Correct 825 ms 45664 KB Ok
98 Correct 563 ms 45724 KB Ok
99 Correct 571 ms 44476 KB Ok
100 Correct 746 ms 45644 KB Ok
101 Correct 704 ms 46452 KB Ok
102 Correct 715 ms 45220 KB Ok
103 Correct 779 ms 47152 KB Ok
104 Correct 884 ms 48092 KB Ok
105 Correct 855 ms 48764 KB Ok
106 Correct 670 ms 47252 KB Ok
107 Correct 785 ms 47308 KB Ok
108 Correct 967 ms 48368 KB Ok
109 Correct 860 ms 50780 KB Ok
110 Execution timed out 2045 ms 58372 KB Time limit exceeded
111 Halted 0 ms 0 KB -