oj.uz

Submission #879405

# Submission time Handle Problem Language Result Execution time Memory
879405 2023-11-27T10:20:48 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
61 / 100
 929 ms 31696 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 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;
        }
    }
    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 79 ms 28116 KB Ok
2 Correct 72 ms 27856 KB Ok
3 Correct 72 ms 20936 KB Ok
4 Correct 65 ms 21196 KB Ok
5 Correct 76 ms 20944 KB Ok
6 Correct 57 ms 22072 KB Ok
7 Correct 64 ms 20944 KB Ok
8 Correct 68 ms 22484 KB Ok
9 Correct 60 ms 20948 KB Ok
10 Correct 69 ms 23816 KB Ok
11 Correct 69 ms 20944 KB Ok
12 Correct 63 ms 20948 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 27248 KB Ok
2 Correct 63 ms 27344 KB Ok
3 Correct 69 ms 27344 KB Ok
4 Correct 67 ms 27340 KB Ok
5 Correct 86 ms 27280 KB Ok
6 Correct 64 ms 27604 KB Ok
7 Correct 82 ms 27604 KB Ok
8 Correct 87 ms 27604 KB Ok
9 Correct 83 ms 27860 KB Ok
10 Correct 81 ms 27588 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27860 KB Ok
2 Correct 65 ms 27712 KB Ok
3 Correct 64 ms 27268 KB Ok
4 Correct 68 ms 27860 KB Ok
5 Correct 69 ms 27852 KB Ok
6 Correct 66 ms 27332 KB Ok
7 Correct 63 ms 27852 KB Ok
8 Correct 65 ms 27860 KB Ok
9 Correct 67 ms 27348 KB Ok
10 Correct 67 ms 27340 KB Ok
11 Correct 66 ms 27344 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 27848 KB Ok
2 Correct 84 ms 28104 KB Ok
3 Correct 69 ms 27860 KB Ok
4 Correct 69 ms 27860 KB Ok
5 Correct 93 ms 27856 KB Ok
6 Incorrect 305 ms 30584 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 79 ms 28116 KB Ok
2 Correct 72 ms 27856 KB Ok
3 Correct 72 ms 20936 KB Ok
4 Correct 65 ms 21196 KB Ok
5 Correct 76 ms 20944 KB Ok
6 Correct 57 ms 22072 KB Ok
7 Correct 64 ms 20944 KB Ok
8 Correct 68 ms 22484 KB Ok
9 Correct 60 ms 20948 KB Ok
10 Correct 69 ms 23816 KB Ok
11 Correct 69 ms 20944 KB Ok
12 Correct 63 ms 20948 KB Ok
13 Correct 33 ms 27860 KB Ok
14 Correct 65 ms 27712 KB Ok
15 Correct 64 ms 27268 KB Ok
16 Correct 68 ms 27860 KB Ok
17 Correct 69 ms 27852 KB Ok
18 Correct 66 ms 27332 KB Ok
19 Correct 63 ms 27852 KB Ok
20 Correct 65 ms 27860 KB Ok
21 Correct 67 ms 27348 KB Ok
22 Correct 67 ms 27340 KB Ok
23 Correct 66 ms 27344 KB Ok
24 Correct 81 ms 20688 KB Ok
25 Correct 99 ms 20840 KB Ok
26 Correct 81 ms 21200 KB Ok
27 Correct 89 ms 20920 KB Ok
28 Correct 84 ms 20688 KB Ok
29 Correct 92 ms 22740 KB Ok
30 Correct 87 ms 20944 KB Ok
31 Correct 84 ms 20736 KB Ok
32 Correct 83 ms 20688 KB Ok
33 Correct 87 ms 20692 KB Ok
34 Correct 134 ms 27504 KB Ok
35 Correct 120 ms 27740 KB Ok
36 Correct 127 ms 27596 KB Ok
37 Correct 165 ms 27604 KB Ok
38 Correct 121 ms 27332 KB Ok
39 Correct 138 ms 27700 KB Ok
40 Correct 130 ms 27616 KB Ok
41 Correct 152 ms 27596 KB Ok
42 Correct 125 ms 27600 KB Ok
43 Correct 115 ms 27848 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 28116 KB Ok
2 Correct 72 ms 27856 KB Ok
3 Correct 72 ms 20936 KB Ok
4 Correct 65 ms 21196 KB Ok
5 Correct 76 ms 20944 KB Ok
6 Correct 57 ms 22072 KB Ok
7 Correct 64 ms 20944 KB Ok
8 Correct 68 ms 22484 KB Ok
9 Correct 60 ms 20948 KB Ok
10 Correct 69 ms 23816 KB Ok
11 Correct 69 ms 20944 KB Ok
12 Correct 63 ms 20948 KB Ok
13 Correct 64 ms 27248 KB Ok
14 Correct 63 ms 27344 KB Ok
15 Correct 69 ms 27344 KB Ok
16 Correct 67 ms 27340 KB Ok
17 Correct 86 ms 27280 KB Ok
18 Correct 64 ms 27604 KB Ok
19 Correct 82 ms 27604 KB Ok
20 Correct 87 ms 27604 KB Ok
21 Correct 83 ms 27860 KB Ok
22 Correct 81 ms 27588 KB Ok
23 Correct 33 ms 27860 KB Ok
24 Correct 65 ms 27712 KB Ok
25 Correct 64 ms 27268 KB Ok
26 Correct 68 ms 27860 KB Ok
27 Correct 69 ms 27852 KB Ok
28 Correct 66 ms 27332 KB Ok
29 Correct 63 ms 27852 KB Ok
30 Correct 65 ms 27860 KB Ok
31 Correct 67 ms 27348 KB Ok
32 Correct 67 ms 27340 KB Ok
33 Correct 66 ms 27344 KB Ok
34 Correct 81 ms 20688 KB Ok
35 Correct 99 ms 20840 KB Ok
36 Correct 81 ms 21200 KB Ok
37 Correct 89 ms 20920 KB Ok
38 Correct 84 ms 20688 KB Ok
39 Correct 92 ms 22740 KB Ok
40 Correct 87 ms 20944 KB Ok
41 Correct 84 ms 20736 KB Ok
42 Correct 83 ms 20688 KB Ok
43 Correct 87 ms 20692 KB Ok
44 Correct 134 ms 27504 KB Ok
45 Correct 120 ms 27740 KB Ok
46 Correct 127 ms 27596 KB Ok
47 Correct 165 ms 27604 KB Ok
48 Correct 121 ms 27332 KB Ok
49 Correct 138 ms 27700 KB Ok
50 Correct 130 ms 27616 KB Ok
51 Correct 152 ms 27596 KB Ok
52 Correct 125 ms 27600 KB Ok
53 Correct 115 ms 27848 KB Ok
54 Correct 215 ms 22348 KB Ok
55 Correct 247 ms 22952 KB Ok
56 Correct 249 ms 22876 KB Ok
57 Correct 179 ms 22216 KB Ok
58 Correct 256 ms 22844 KB Ok
59 Correct 243 ms 22728 KB Ok
60 Correct 187 ms 22360 KB Ok
61 Correct 176 ms 22216 KB Ok
62 Correct 268 ms 22976 KB Ok
63 Correct 219 ms 22676 KB Ok
64 Correct 257 ms 22984 KB Ok
65 Correct 226 ms 22724 KB Ok
66 Correct 189 ms 22472 KB Ok
67 Correct 178 ms 22212 KB Ok
68 Correct 237 ms 22492 KB Ok
69 Correct 887 ms 31184 KB Ok
70 Correct 910 ms 31552 KB Ok
71 Correct 877 ms 31084 KB Ok
72 Correct 778 ms 30896 KB Ok
73 Correct 929 ms 31348 KB Ok
74 Correct 713 ms 31020 KB Ok
75 Correct 835 ms 31060 KB Ok
76 Correct 758 ms 31280 KB Ok
77 Correct 707 ms 31012 KB Ok
78 Correct 737 ms 31260 KB Ok
79 Correct 762 ms 31460 KB Ok
80 Correct 721 ms 31144 KB Ok
81 Correct 759 ms 31696 KB Ok
82 Correct 738 ms 31488 KB Ok
83 Correct 750 ms 31276 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 28116 KB Ok
2 Correct 72 ms 27856 KB Ok
3 Correct 72 ms 20936 KB Ok
4 Correct 65 ms 21196 KB Ok
5 Correct 76 ms 20944 KB Ok
6 Correct 57 ms 22072 KB Ok
7 Correct 64 ms 20944 KB Ok
8 Correct 68 ms 22484 KB Ok
9 Correct 60 ms 20948 KB Ok
10 Correct 69 ms 23816 KB Ok
11 Correct 69 ms 20944 KB Ok
12 Correct 63 ms 20948 KB Ok
13 Correct 64 ms 27248 KB Ok
14 Correct 63 ms 27344 KB Ok
15 Correct 69 ms 27344 KB Ok
16 Correct 67 ms 27340 KB Ok
17 Correct 86 ms 27280 KB Ok
18 Correct 64 ms 27604 KB Ok
19 Correct 82 ms 27604 KB Ok
20 Correct 87 ms 27604 KB Ok
21 Correct 83 ms 27860 KB Ok
22 Correct 81 ms 27588 KB Ok
23 Correct 33 ms 27860 KB Ok
24 Correct 65 ms 27712 KB Ok
25 Correct 64 ms 27268 KB Ok
26 Correct 68 ms 27860 KB Ok
27 Correct 69 ms 27852 KB Ok
28 Correct 66 ms 27332 KB Ok
29 Correct 63 ms 27852 KB Ok
30 Correct 65 ms 27860 KB Ok
31 Correct 67 ms 27348 KB Ok
32 Correct 67 ms 27340 KB Ok
33 Correct 66 ms 27344 KB Ok
34 Correct 65 ms 27848 KB Ok
35 Correct 84 ms 28104 KB Ok
36 Correct 69 ms 27860 KB Ok
37 Correct 69 ms 27860 KB Ok
38 Correct 93 ms 27856 KB Ok
39 Incorrect 305 ms 30584 KB Jury has the better answer : jans = 166803, pans = 149999
40 Halted 0 ms 0 KB -