oj.uz

Submission #879428

# Submission time Handle Problem Language Result Execution time Memory
879428 2023-11-27T10:57:32 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 54596 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
const int N = 1e6 + 10, MOD = 998244353;
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = 1;
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){
  	assert(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;
    }
  	bool ans = ok;
  	ok = 1;
    return ans;
}
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 90 ms 40640 KB Ok
2 Correct 87 ms 40660 KB Ok
3 Correct 154 ms 34772 KB Ok
4 Correct 140 ms 35264 KB Ok
5 Correct 185 ms 34896 KB Ok
6 Correct 150 ms 35876 KB Ok
7 Correct 129 ms 34772 KB Ok
8 Correct 153 ms 36052 KB Ok
9 Correct 152 ms 34812 KB Ok
10 Correct 166 ms 37572 KB Ok
11 Correct 142 ms 34764 KB Ok
12 Correct 207 ms 34772 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 40388 KB Ok
2 Correct 84 ms 40304 KB Ok
3 Correct 110 ms 40380 KB Ok
4 Correct 108 ms 40400 KB Ok
5 Correct 93 ms 40400 KB Ok
6 Correct 90 ms 40404 KB Ok
7 Correct 100 ms 40600 KB Ok
8 Correct 92 ms 40400 KB Ok
9 Correct 113 ms 41052 KB Ok
10 Correct 94 ms 40388 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 40660 KB Ok
2 Correct 85 ms 40392 KB Ok
3 Correct 86 ms 40132 KB Ok
4 Correct 85 ms 40656 KB Ok
5 Correct 86 ms 40588 KB Ok
6 Correct 88 ms 40400 KB Ok
7 Correct 85 ms 40404 KB Ok
8 Correct 96 ms 40404 KB Ok
9 Correct 86 ms 40248 KB Ok
10 Correct 91 ms 40400 KB Ok
11 Correct 86 ms 40248 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 40392 KB Ok
2 Correct 107 ms 40432 KB Ok
3 Correct 105 ms 40392 KB Ok
4 Correct 100 ms 40404 KB Ok
5 Correct 108 ms 40404 KB Ok
6 Correct 311 ms 43912 KB Ok
7 Correct 234 ms 42436 KB Ok
8 Correct 469 ms 45072 KB Ok
9 Correct 337 ms 45976 KB Ok
10 Correct 223 ms 42836 KB Ok
11 Correct 367 ms 45400 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 40640 KB Ok
2 Correct 87 ms 40660 KB Ok
3 Correct 154 ms 34772 KB Ok
4 Correct 140 ms 35264 KB Ok
5 Correct 185 ms 34896 KB Ok
6 Correct 150 ms 35876 KB Ok
7 Correct 129 ms 34772 KB Ok
8 Correct 153 ms 36052 KB Ok
9 Correct 152 ms 34812 KB Ok
10 Correct 166 ms 37572 KB Ok
11 Correct 142 ms 34764 KB Ok
12 Correct 207 ms 34772 KB Ok
13 Correct 41 ms 40660 KB Ok
14 Correct 85 ms 40392 KB Ok
15 Correct 86 ms 40132 KB Ok
16 Correct 85 ms 40656 KB Ok
17 Correct 86 ms 40588 KB Ok
18 Correct 88 ms 40400 KB Ok
19 Correct 85 ms 40404 KB Ok
20 Correct 96 ms 40404 KB Ok
21 Correct 86 ms 40248 KB Ok
22 Correct 91 ms 40400 KB Ok
23 Correct 86 ms 40248 KB Ok
24 Correct 122 ms 34516 KB Ok
25 Correct 125 ms 34656 KB Ok
26 Correct 121 ms 35028 KB Ok
27 Correct 140 ms 34760 KB Ok
28 Correct 152 ms 34516 KB Ok
29 Correct 125 ms 36556 KB Ok
30 Correct 120 ms 34772 KB Ok
31 Correct 128 ms 34628 KB Ok
32 Correct 132 ms 34772 KB Ok
33 Correct 121 ms 35016 KB Ok
34 Correct 182 ms 40444 KB Ok
35 Correct 158 ms 40496 KB Ok
36 Correct 177 ms 40644 KB Ok
37 Correct 147 ms 40392 KB Ok
38 Correct 155 ms 40388 KB Ok
39 Correct 171 ms 40520 KB Ok
40 Correct 215 ms 40400 KB Ok
41 Correct 169 ms 40364 KB Ok
42 Correct 226 ms 40396 KB Ok
43 Correct 161 ms 40520 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 40640 KB Ok
2 Correct 87 ms 40660 KB Ok
3 Correct 154 ms 34772 KB Ok
4 Correct 140 ms 35264 KB Ok
5 Correct 185 ms 34896 KB Ok
6 Correct 150 ms 35876 KB Ok
7 Correct 129 ms 34772 KB Ok
8 Correct 153 ms 36052 KB Ok
9 Correct 152 ms 34812 KB Ok
10 Correct 166 ms 37572 KB Ok
11 Correct 142 ms 34764 KB Ok
12 Correct 207 ms 34772 KB Ok
13 Correct 83 ms 40388 KB Ok
14 Correct 84 ms 40304 KB Ok
15 Correct 110 ms 40380 KB Ok
16 Correct 108 ms 40400 KB Ok
17 Correct 93 ms 40400 KB Ok
18 Correct 90 ms 40404 KB Ok
19 Correct 100 ms 40600 KB Ok
20 Correct 92 ms 40400 KB Ok
21 Correct 113 ms 41052 KB Ok
22 Correct 94 ms 40388 KB Ok
23 Correct 41 ms 40660 KB Ok
24 Correct 85 ms 40392 KB Ok
25 Correct 86 ms 40132 KB Ok
26 Correct 85 ms 40656 KB Ok
27 Correct 86 ms 40588 KB Ok
28 Correct 88 ms 40400 KB Ok
29 Correct 85 ms 40404 KB Ok
30 Correct 96 ms 40404 KB Ok
31 Correct 86 ms 40248 KB Ok
32 Correct 91 ms 40400 KB Ok
33 Correct 86 ms 40248 KB Ok
34 Correct 122 ms 34516 KB Ok
35 Correct 125 ms 34656 KB Ok
36 Correct 121 ms 35028 KB Ok
37 Correct 140 ms 34760 KB Ok
38 Correct 152 ms 34516 KB Ok
39 Correct 125 ms 36556 KB Ok
40 Correct 120 ms 34772 KB Ok
41 Correct 128 ms 34628 KB Ok
42 Correct 132 ms 34772 KB Ok
43 Correct 121 ms 35016 KB Ok
44 Correct 182 ms 40444 KB Ok
45 Correct 158 ms 40496 KB Ok
46 Correct 177 ms 40644 KB Ok
47 Correct 147 ms 40392 KB Ok
48 Correct 155 ms 40388 KB Ok
49 Correct 171 ms 40520 KB Ok
50 Correct 215 ms 40400 KB Ok
51 Correct 169 ms 40364 KB Ok
52 Correct 226 ms 40396 KB Ok
53 Correct 161 ms 40520 KB Ok
54 Correct 193 ms 36548 KB Ok
55 Correct 232 ms 37096 KB Ok
56 Correct 219 ms 36832 KB Ok
57 Correct 161 ms 36036 KB Ok
58 Correct 243 ms 36816 KB Ok
59 Correct 200 ms 36628 KB Ok
60 Correct 183 ms 36364 KB Ok
61 Correct 172 ms 36324 KB Ok
62 Correct 251 ms 37068 KB Ok
63 Correct 197 ms 36544 KB Ok
64 Correct 258 ms 37056 KB Ok
65 Correct 212 ms 36808 KB Ok
66 Correct 180 ms 36556 KB Ok
67 Correct 172 ms 36264 KB Ok
68 Correct 221 ms 36552 KB Ok
69 Correct 773 ms 46508 KB Ok
70 Correct 860 ms 46784 KB Ok
71 Correct 842 ms 46532 KB Ok
72 Correct 718 ms 46404 KB Ok
73 Correct 721 ms 46824 KB Ok
74 Correct 740 ms 46272 KB Ok
75 Correct 766 ms 46496 KB Ok
76 Correct 747 ms 46528 KB Ok
77 Correct 674 ms 46408 KB Ok
78 Correct 702 ms 46408 KB Ok
79 Correct 688 ms 46784 KB Ok
80 Correct 777 ms 46276 KB Ok
81 Correct 647 ms 46780 KB Ok
82 Correct 821 ms 46552 KB Ok
83 Correct 784 ms 46568 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 40640 KB Ok
2 Correct 87 ms 40660 KB Ok
3 Correct 154 ms 34772 KB Ok
4 Correct 140 ms 35264 KB Ok
5 Correct 185 ms 34896 KB Ok
6 Correct 150 ms 35876 KB Ok
7 Correct 129 ms 34772 KB Ok
8 Correct 153 ms 36052 KB Ok
9 Correct 152 ms 34812 KB Ok
10 Correct 166 ms 37572 KB Ok
11 Correct 142 ms 34764 KB Ok
12 Correct 207 ms 34772 KB Ok
13 Correct 83 ms 40388 KB Ok
14 Correct 84 ms 40304 KB Ok
15 Correct 110 ms 40380 KB Ok
16 Correct 108 ms 40400 KB Ok
17 Correct 93 ms 40400 KB Ok
18 Correct 90 ms 40404 KB Ok
19 Correct 100 ms 40600 KB Ok
20 Correct 92 ms 40400 KB Ok
21 Correct 113 ms 41052 KB Ok
22 Correct 94 ms 40388 KB Ok
23 Correct 41 ms 40660 KB Ok
24 Correct 85 ms 40392 KB Ok
25 Correct 86 ms 40132 KB Ok
26 Correct 85 ms 40656 KB Ok
27 Correct 86 ms 40588 KB Ok
28 Correct 88 ms 40400 KB Ok
29 Correct 85 ms 40404 KB Ok
30 Correct 96 ms 40404 KB Ok
31 Correct 86 ms 40248 KB Ok
32 Correct 91 ms 40400 KB Ok
33 Correct 86 ms 40248 KB Ok
34 Correct 95 ms 40392 KB Ok
35 Correct 107 ms 40432 KB Ok
36 Correct 105 ms 40392 KB Ok
37 Correct 100 ms 40404 KB Ok
38 Correct 108 ms 40404 KB Ok
39 Correct 311 ms 43912 KB Ok
40 Correct 234 ms 42436 KB Ok
41 Correct 469 ms 45072 KB Ok
42 Correct 337 ms 45976 KB Ok
43 Correct 223 ms 42836 KB Ok
44 Correct 367 ms 45400 KB Ok
45 Correct 122 ms 34516 KB Ok
46 Correct 125 ms 34656 KB Ok
47 Correct 121 ms 35028 KB Ok
48 Correct 140 ms 34760 KB Ok
49 Correct 152 ms 34516 KB Ok
50 Correct 125 ms 36556 KB Ok
51 Correct 120 ms 34772 KB Ok
52 Correct 128 ms 34628 KB Ok
53 Correct 132 ms 34772 KB Ok
54 Correct 121 ms 35016 KB Ok
55 Correct 182 ms 40444 KB Ok
56 Correct 158 ms 40496 KB Ok
57 Correct 177 ms 40644 KB Ok
58 Correct 147 ms 40392 KB Ok
59 Correct 155 ms 40388 KB Ok
60 Correct 171 ms 40520 KB Ok
61 Correct 215 ms 40400 KB Ok
62 Correct 169 ms 40364 KB Ok
63 Correct 226 ms 40396 KB Ok
64 Correct 161 ms 40520 KB Ok
65 Correct 193 ms 36548 KB Ok
66 Correct 232 ms 37096 KB Ok
67 Correct 219 ms 36832 KB Ok
68 Correct 161 ms 36036 KB Ok
69 Correct 243 ms 36816 KB Ok
70 Correct 200 ms 36628 KB Ok
71 Correct 183 ms 36364 KB Ok
72 Correct 172 ms 36324 KB Ok
73 Correct 251 ms 37068 KB Ok
74 Correct 197 ms 36544 KB Ok
75 Correct 258 ms 37056 KB Ok
76 Correct 212 ms 36808 KB Ok
77 Correct 180 ms 36556 KB Ok
78 Correct 172 ms 36264 KB Ok
79 Correct 221 ms 36552 KB Ok
80 Correct 773 ms 46508 KB Ok
81 Correct 860 ms 46784 KB Ok
82 Correct 842 ms 46532 KB Ok
83 Correct 718 ms 46404 KB Ok
84 Correct 721 ms 46824 KB Ok
85 Correct 740 ms 46272 KB Ok
86 Correct 766 ms 46496 KB Ok
87 Correct 747 ms 46528 KB Ok
88 Correct 674 ms 46408 KB Ok
89 Correct 702 ms 46408 KB Ok
90 Correct 688 ms 46784 KB Ok
91 Correct 777 ms 46276 KB Ok
92 Correct 647 ms 46780 KB Ok
93 Correct 821 ms 46552 KB Ok
94 Correct 784 ms 46568 KB Ok
95 Correct 521 ms 43444 KB Ok
96 Correct 753 ms 48996 KB Ok
97 Correct 686 ms 45552 KB Ok
98 Correct 467 ms 45508 KB Ok
99 Correct 490 ms 44420 KB Ok
100 Correct 638 ms 45556 KB Ok
101 Correct 558 ms 46524 KB Ok
102 Correct 593 ms 45032 KB Ok
103 Correct 662 ms 47064 KB Ok
104 Correct 795 ms 48060 KB Ok
105 Correct 743 ms 48828 KB Ok
106 Correct 611 ms 47348 KB Ok
107 Correct 730 ms 47312 KB Ok
108 Correct 938 ms 48568 KB Ok
109 Correct 729 ms 50628 KB Ok
110 Execution timed out 2025 ms 54596 KB Time limit exceeded
111 Halted 0 ms 0 KB -