oj.uz

Submission #879411

# Submission time Handle Problem Language Result Execution time Memory
879411 2023-11-27T10:28:23 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 1446 ms 53484 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);
        }
        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++;
    }
    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 = 5e5;
    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 161 ms 47828 KB Ok
2 Correct 138 ms 47828 KB Ok
3 Correct 159 ms 37064 KB Ok
4 Correct 137 ms 37704 KB Ok
5 Correct 155 ms 37076 KB Ok
6 Correct 127 ms 39112 KB Ok
7 Correct 144 ms 36816 KB Ok
8 Correct 123 ms 39120 KB Ok
9 Correct 116 ms 36812 KB Ok
10 Correct 148 ms 42072 KB Ok
11 Correct 137 ms 36816 KB Ok
12 Correct 117 ms 36560 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 47820 KB Ok
2 Correct 161 ms 47820 KB Ok
3 Correct 182 ms 47824 KB Ok
4 Correct 147 ms 47812 KB Ok
5 Correct 152 ms 47928 KB Ok
6 Correct 146 ms 48004 KB Ok
7 Correct 136 ms 48072 KB Ok
8 Correct 137 ms 47924 KB Ok
9 Correct 149 ms 48388 KB Ok
10 Correct 132 ms 47904 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 47828 KB Ok
2 Correct 130 ms 47816 KB Ok
3 Correct 127 ms 47820 KB Ok
4 Correct 144 ms 47832 KB Ok
5 Correct 151 ms 47836 KB Ok
6 Correct 128 ms 47828 KB Ok
7 Correct 130 ms 47832 KB Ok
8 Correct 129 ms 47904 KB Ok
9 Correct 141 ms 47824 KB Ok
10 Correct 149 ms 47832 KB Ok
11 Correct 158 ms 47824 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 47824 KB Ok
2 Correct 129 ms 47828 KB Ok
3 Correct 168 ms 47904 KB Ok
4 Correct 185 ms 47832 KB Ok
5 Correct 174 ms 47828 KB Ok
6 Correct 429 ms 51468 KB Ok
7 Correct 347 ms 50252 KB Ok
8 Correct 750 ms 52688 KB Ok
9 Correct 440 ms 53484 KB Ok
10 Correct 336 ms 50380 KB Ok
11 Correct 476 ms 53008 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47828 KB Ok
2 Correct 138 ms 47828 KB Ok
3 Correct 159 ms 37064 KB Ok
4 Correct 137 ms 37704 KB Ok
5 Correct 155 ms 37076 KB Ok
6 Correct 127 ms 39112 KB Ok
7 Correct 144 ms 36816 KB Ok
8 Correct 123 ms 39120 KB Ok
9 Correct 116 ms 36812 KB Ok
10 Correct 148 ms 42072 KB Ok
11 Correct 137 ms 36816 KB Ok
12 Correct 117 ms 36560 KB Ok
13 Correct 58 ms 47828 KB Ok
14 Correct 130 ms 47816 KB Ok
15 Correct 127 ms 47820 KB Ok
16 Correct 144 ms 47832 KB Ok
17 Correct 151 ms 47836 KB Ok
18 Correct 128 ms 47828 KB Ok
19 Correct 130 ms 47832 KB Ok
20 Correct 129 ms 47904 KB Ok
21 Correct 141 ms 47824 KB Ok
22 Correct 149 ms 47832 KB Ok
23 Correct 158 ms 47824 KB Ok
24 Correct 147 ms 36316 KB Ok
25 Correct 158 ms 36484 KB Ok
26 Correct 156 ms 37076 KB Ok
27 Correct 177 ms 37112 KB Ok
28 Correct 159 ms 36304 KB Ok
29 Correct 157 ms 39984 KB Ok
30 Correct 177 ms 36796 KB Ok
31 Correct 169 ms 36704 KB Ok
32 Correct 182 ms 36440 KB Ok
33 Correct 157 ms 36808 KB Ok
34 Correct 367 ms 48220 KB Ok
35 Correct 249 ms 48080 KB Ok
36 Correct 310 ms 48024 KB Ok
37 Correct 321 ms 48128 KB Ok
38 Correct 261 ms 47972 KB Ok
39 Correct 397 ms 48052 KB Ok
40 Correct 288 ms 48076 KB Ok
41 Correct 242 ms 48132 KB Ok
42 Correct 363 ms 47996 KB Ok
43 Correct 270 ms 48016 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47828 KB Ok
2 Correct 138 ms 47828 KB Ok
3 Correct 159 ms 37064 KB Ok
4 Correct 137 ms 37704 KB Ok
5 Correct 155 ms 37076 KB Ok
6 Correct 127 ms 39112 KB Ok
7 Correct 144 ms 36816 KB Ok
8 Correct 123 ms 39120 KB Ok
9 Correct 116 ms 36812 KB Ok
10 Correct 148 ms 42072 KB Ok
11 Correct 137 ms 36816 KB Ok
12 Correct 117 ms 36560 KB Ok
13 Correct 120 ms 47820 KB Ok
14 Correct 161 ms 47820 KB Ok
15 Correct 182 ms 47824 KB Ok
16 Correct 147 ms 47812 KB Ok
17 Correct 152 ms 47928 KB Ok
18 Correct 146 ms 48004 KB Ok
19 Correct 136 ms 48072 KB Ok
20 Correct 137 ms 47924 KB Ok
21 Correct 149 ms 48388 KB Ok
22 Correct 132 ms 47904 KB Ok
23 Correct 58 ms 47828 KB Ok
24 Correct 130 ms 47816 KB Ok
25 Correct 127 ms 47820 KB Ok
26 Correct 144 ms 47832 KB Ok
27 Correct 151 ms 47836 KB Ok
28 Correct 128 ms 47828 KB Ok
29 Correct 130 ms 47832 KB Ok
30 Correct 129 ms 47904 KB Ok
31 Correct 141 ms 47824 KB Ok
32 Correct 149 ms 47832 KB Ok
33 Correct 158 ms 47824 KB Ok
34 Correct 147 ms 36316 KB Ok
35 Correct 158 ms 36484 KB Ok
36 Correct 156 ms 37076 KB Ok
37 Correct 177 ms 37112 KB Ok
38 Correct 159 ms 36304 KB Ok
39 Correct 157 ms 39984 KB Ok
40 Correct 177 ms 36796 KB Ok
41 Correct 169 ms 36704 KB Ok
42 Correct 182 ms 36440 KB Ok
43 Correct 157 ms 36808 KB Ok
44 Correct 367 ms 48220 KB Ok
45 Correct 249 ms 48080 KB Ok
46 Correct 310 ms 48024 KB Ok
47 Correct 321 ms 48128 KB Ok
48 Correct 261 ms 47972 KB Ok
49 Correct 397 ms 48052 KB Ok
50 Correct 288 ms 48076 KB Ok
51 Correct 242 ms 48132 KB Ok
52 Correct 363 ms 47996 KB Ok
53 Correct 270 ms 48016 KB Ok
54 Correct 269 ms 38228 KB Ok
55 Correct 285 ms 38780 KB Ok
56 Correct 299 ms 38692 KB Ok
57 Correct 209 ms 37864 KB Ok
58 Correct 288 ms 38528 KB Ok
59 Correct 260 ms 38352 KB Ok
60 Correct 244 ms 38076 KB Ok
61 Correct 223 ms 38092 KB Ok
62 Correct 306 ms 39040 KB Ok
63 Correct 256 ms 38304 KB Ok
64 Correct 336 ms 38728 KB Ok
65 Correct 280 ms 38640 KB Ok
66 Correct 248 ms 38208 KB Ok
67 Correct 234 ms 38048 KB Ok
68 Correct 288 ms 38556 KB Ok
69 Correct 1014 ms 51660 KB Ok
70 Correct 957 ms 52144 KB Ok
71 Correct 954 ms 51916 KB Ok
72 Correct 876 ms 51664 KB Ok
73 Correct 960 ms 52172 KB Ok
74 Correct 938 ms 51556 KB Ok
75 Correct 995 ms 51680 KB Ok
76 Correct 975 ms 51772 KB Ok
77 Correct 941 ms 51476 KB Ok
78 Correct 1289 ms 51444 KB Ok
79 Correct 1446 ms 51912 KB Ok
80 Correct 881 ms 51660 KB Ok
81 Correct 1044 ms 52036 KB Ok
82 Correct 947 ms 51728 KB Ok
83 Correct 959 ms 51616 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 47828 KB Ok
2 Correct 138 ms 47828 KB Ok
3 Correct 159 ms 37064 KB Ok
4 Correct 137 ms 37704 KB Ok
5 Correct 155 ms 37076 KB Ok
6 Correct 127 ms 39112 KB Ok
7 Correct 144 ms 36816 KB Ok
8 Correct 123 ms 39120 KB Ok
9 Correct 116 ms 36812 KB Ok
10 Correct 148 ms 42072 KB Ok
11 Correct 137 ms 36816 KB Ok
12 Correct 117 ms 36560 KB Ok
13 Correct 120 ms 47820 KB Ok
14 Correct 161 ms 47820 KB Ok
15 Correct 182 ms 47824 KB Ok
16 Correct 147 ms 47812 KB Ok
17 Correct 152 ms 47928 KB Ok
18 Correct 146 ms 48004 KB Ok
19 Correct 136 ms 48072 KB Ok
20 Correct 137 ms 47924 KB Ok
21 Correct 149 ms 48388 KB Ok
22 Correct 132 ms 47904 KB Ok
23 Correct 58 ms 47828 KB Ok
24 Correct 130 ms 47816 KB Ok
25 Correct 127 ms 47820 KB Ok
26 Correct 144 ms 47832 KB Ok
27 Correct 151 ms 47836 KB Ok
28 Correct 128 ms 47828 KB Ok
29 Correct 130 ms 47832 KB Ok
30 Correct 129 ms 47904 KB Ok
31 Correct 141 ms 47824 KB Ok
32 Correct 149 ms 47832 KB Ok
33 Correct 158 ms 47824 KB Ok
34 Correct 136 ms 47824 KB Ok
35 Correct 129 ms 47828 KB Ok
36 Correct 168 ms 47904 KB Ok
37 Correct 185 ms 47832 KB Ok
38 Correct 174 ms 47828 KB Ok
39 Correct 429 ms 51468 KB Ok
40 Correct 347 ms 50252 KB Ok
41 Correct 750 ms 52688 KB Ok
42 Correct 440 ms 53484 KB Ok
43 Correct 336 ms 50380 KB Ok
44 Correct 476 ms 53008 KB Ok
45 Correct 147 ms 36316 KB Ok
46 Correct 158 ms 36484 KB Ok
47 Correct 156 ms 37076 KB Ok
48 Correct 177 ms 37112 KB Ok
49 Correct 159 ms 36304 KB Ok
50 Correct 157 ms 39984 KB Ok
51 Correct 177 ms 36796 KB Ok
52 Correct 169 ms 36704 KB Ok
53 Correct 182 ms 36440 KB Ok
54 Correct 157 ms 36808 KB Ok
55 Correct 367 ms 48220 KB Ok
56 Correct 249 ms 48080 KB Ok
57 Correct 310 ms 48024 KB Ok
58 Correct 321 ms 48128 KB Ok
59 Correct 261 ms 47972 KB Ok
60 Correct 397 ms 48052 KB Ok
61 Correct 288 ms 48076 KB Ok
62 Correct 242 ms 48132 KB Ok
63 Correct 363 ms 47996 KB Ok
64 Correct 270 ms 48016 KB Ok
65 Correct 269 ms 38228 KB Ok
66 Correct 285 ms 38780 KB Ok
67 Correct 299 ms 38692 KB Ok
68 Correct 209 ms 37864 KB Ok
69 Correct 288 ms 38528 KB Ok
70 Correct 260 ms 38352 KB Ok
71 Correct 244 ms 38076 KB Ok
72 Correct 223 ms 38092 KB Ok
73 Correct 306 ms 39040 KB Ok
74 Correct 256 ms 38304 KB Ok
75 Correct 336 ms 38728 KB Ok
76 Correct 280 ms 38640 KB Ok
77 Correct 248 ms 38208 KB Ok
78 Correct 234 ms 38048 KB Ok
79 Correct 288 ms 38556 KB Ok
80 Correct 1014 ms 51660 KB Ok
81 Correct 957 ms 52144 KB Ok
82 Correct 954 ms 51916 KB Ok
83 Correct 876 ms 51664 KB Ok
84 Correct 960 ms 52172 KB Ok
85 Correct 938 ms 51556 KB Ok
86 Correct 995 ms 51680 KB Ok
87 Correct 975 ms 51772 KB Ok
88 Correct 941 ms 51476 KB Ok
89 Correct 1289 ms 51444 KB Ok
90 Correct 1446 ms 51912 KB Ok
91 Correct 881 ms 51660 KB Ok
92 Correct 1044 ms 52036 KB Ok
93 Correct 947 ms 51728 KB Ok
94 Correct 959 ms 51616 KB Ok
95 Correct 586 ms 41932 KB Ok
96 Incorrect 894 ms 48920 KB Jury has the better answer : jans = 280751, pans = 249999
97 Halted 0 ms 0 KB -