oj.uz

Submission #879427

# Submission time Handle Problem Language Result Execution time Memory
879427 2023-11-27T10:56:52 Z dimashhh Nice sequence (IZhO18_sequence) C++17
76 / 100
 838 ms 45800 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 = 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 62 ms 37584 KB Ok
2 Correct 65 ms 37440 KB Ok
3 Correct 93 ms 32980 KB Ok
4 Correct 111 ms 33236 KB Ok
5 Correct 99 ms 33492 KB Ok
6 Correct 92 ms 33724 KB Ok
7 Correct 89 ms 33232 KB Ok
8 Correct 96 ms 34256 KB Ok
9 Correct 108 ms 32968 KB Ok
10 Correct 101 ms 34760 KB Ok
11 Correct 103 ms 33236 KB Ok
12 Correct 122 ms 33232 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 36920 KB Ok
2 Correct 61 ms 37060 KB Ok
3 Correct 81 ms 37068 KB Ok
4 Correct 64 ms 37068 KB Ok
5 Correct 68 ms 37060 KB Ok
6 Correct 63 ms 37464 KB Ok
7 Correct 80 ms 37328 KB Ok
8 Correct 70 ms 37332 KB Ok
9 Correct 93 ms 37600 KB Ok
10 Correct 67 ms 37320 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37588 KB Ok
2 Correct 60 ms 37588 KB Ok
3 Correct 71 ms 37064 KB Ok
4 Correct 72 ms 37584 KB Ok
5 Correct 61 ms 37588 KB Ok
6 Correct 64 ms 37072 KB Ok
7 Correct 60 ms 37584 KB Ok
8 Correct 65 ms 37584 KB Ok
9 Correct 63 ms 37064 KB Ok
10 Correct 63 ms 37068 KB Ok
11 Correct 62 ms 37060 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 37588 KB Ok
2 Correct 66 ms 37588 KB Ok
3 Correct 71 ms 37584 KB Ok
4 Correct 75 ms 37588 KB Ok
5 Correct 88 ms 37580 KB Ok
6 Correct 314 ms 43200 KB Ok
7 Correct 238 ms 43148 KB Ok
8 Correct 486 ms 45504 KB Ok
9 Correct 341 ms 45800 KB Ok
10 Correct 200 ms 39680 KB Ok
11 Correct 339 ms 45764 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37584 KB Ok
2 Correct 65 ms 37440 KB Ok
3 Correct 93 ms 32980 KB Ok
4 Correct 111 ms 33236 KB Ok
5 Correct 99 ms 33492 KB Ok
6 Correct 92 ms 33724 KB Ok
7 Correct 89 ms 33232 KB Ok
8 Correct 96 ms 34256 KB Ok
9 Correct 108 ms 32968 KB Ok
10 Correct 101 ms 34760 KB Ok
11 Correct 103 ms 33236 KB Ok
12 Correct 122 ms 33232 KB Ok
13 Correct 30 ms 37588 KB Ok
14 Correct 60 ms 37588 KB Ok
15 Correct 71 ms 37064 KB Ok
16 Correct 72 ms 37584 KB Ok
17 Correct 61 ms 37588 KB Ok
18 Correct 64 ms 37072 KB Ok
19 Correct 60 ms 37584 KB Ok
20 Correct 65 ms 37584 KB Ok
21 Correct 63 ms 37064 KB Ok
22 Correct 63 ms 37068 KB Ok
23 Correct 62 ms 37060 KB Ok
24 Correct 80 ms 32976 KB Ok
25 Correct 113 ms 33148 KB Ok
26 Correct 96 ms 33444 KB Ok
27 Correct 92 ms 32976 KB Ok
28 Correct 87 ms 32976 KB Ok
29 Correct 78 ms 34008 KB Ok
30 Correct 97 ms 33244 KB Ok
31 Correct 89 ms 32980 KB Ok
32 Correct 81 ms 32976 KB Ok
33 Correct 95 ms 32968 KB Ok
34 Correct 144 ms 37184 KB Ok
35 Correct 92 ms 37332 KB Ok
36 Correct 111 ms 37316 KB Ok
37 Correct 99 ms 37328 KB Ok
38 Correct 114 ms 37256 KB Ok
39 Correct 109 ms 37056 KB Ok
40 Correct 125 ms 37328 KB Ok
41 Correct 94 ms 37328 KB Ok
42 Correct 120 ms 37328 KB Ok
43 Correct 98 ms 37324 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37584 KB Ok
2 Correct 65 ms 37440 KB Ok
3 Correct 93 ms 32980 KB Ok
4 Correct 111 ms 33236 KB Ok
5 Correct 99 ms 33492 KB Ok
6 Correct 92 ms 33724 KB Ok
7 Correct 89 ms 33232 KB Ok
8 Correct 96 ms 34256 KB Ok
9 Correct 108 ms 32968 KB Ok
10 Correct 101 ms 34760 KB Ok
11 Correct 103 ms 33236 KB Ok
12 Correct 122 ms 33232 KB Ok
13 Correct 60 ms 36920 KB Ok
14 Correct 61 ms 37060 KB Ok
15 Correct 81 ms 37068 KB Ok
16 Correct 64 ms 37068 KB Ok
17 Correct 68 ms 37060 KB Ok
18 Correct 63 ms 37464 KB Ok
19 Correct 80 ms 37328 KB Ok
20 Correct 70 ms 37332 KB Ok
21 Correct 93 ms 37600 KB Ok
22 Correct 67 ms 37320 KB Ok
23 Correct 30 ms 37588 KB Ok
24 Correct 60 ms 37588 KB Ok
25 Correct 71 ms 37064 KB Ok
26 Correct 72 ms 37584 KB Ok
27 Correct 61 ms 37588 KB Ok
28 Correct 64 ms 37072 KB Ok
29 Correct 60 ms 37584 KB Ok
30 Correct 65 ms 37584 KB Ok
31 Correct 63 ms 37064 KB Ok
32 Correct 63 ms 37068 KB Ok
33 Correct 62 ms 37060 KB Ok
34 Correct 80 ms 32976 KB Ok
35 Correct 113 ms 33148 KB Ok
36 Correct 96 ms 33444 KB Ok
37 Correct 92 ms 32976 KB Ok
38 Correct 87 ms 32976 KB Ok
39 Correct 78 ms 34008 KB Ok
40 Correct 97 ms 33244 KB Ok
41 Correct 89 ms 32980 KB Ok
42 Correct 81 ms 32976 KB Ok
43 Correct 95 ms 32968 KB Ok
44 Correct 144 ms 37184 KB Ok
45 Correct 92 ms 37332 KB Ok
46 Correct 111 ms 37316 KB Ok
47 Correct 99 ms 37328 KB Ok
48 Correct 114 ms 37256 KB Ok
49 Correct 109 ms 37056 KB Ok
50 Correct 125 ms 37328 KB Ok
51 Correct 94 ms 37328 KB Ok
52 Correct 120 ms 37328 KB Ok
53 Correct 98 ms 37324 KB Ok
54 Correct 173 ms 34756 KB Ok
55 Correct 202 ms 35256 KB Ok
56 Correct 210 ms 35012 KB Ok
57 Correct 139 ms 34264 KB Ok
58 Correct 207 ms 34960 KB Ok
59 Correct 197 ms 35008 KB Ok
60 Correct 167 ms 34500 KB Ok
61 Correct 147 ms 34504 KB Ok
62 Correct 222 ms 35288 KB Ok
63 Correct 176 ms 34660 KB Ok
64 Correct 231 ms 35212 KB Ok
65 Correct 210 ms 35148 KB Ok
66 Correct 160 ms 34756 KB Ok
67 Correct 158 ms 34504 KB Ok
68 Correct 188 ms 35012 KB Ok
69 Correct 718 ms 41644 KB Ok
70 Correct 710 ms 42020 KB Ok
71 Correct 832 ms 41640 KB Ok
72 Correct 724 ms 41588 KB Ok
73 Correct 838 ms 41956 KB Ok
74 Correct 736 ms 41656 KB Ok
75 Correct 715 ms 41668 KB Ok
76 Correct 718 ms 41920 KB Ok
77 Correct 799 ms 41768 KB Ok
78 Correct 687 ms 41552 KB Ok
79 Correct 734 ms 42120 KB Ok
80 Correct 693 ms 41672 KB Ok
81 Correct 826 ms 41924 KB Ok
82 Correct 662 ms 41952 KB Ok
83 Correct 685 ms 41896 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37584 KB Ok
2 Correct 65 ms 37440 KB Ok
3 Correct 93 ms 32980 KB Ok
4 Correct 111 ms 33236 KB Ok
5 Correct 99 ms 33492 KB Ok
6 Correct 92 ms 33724 KB Ok
7 Correct 89 ms 33232 KB Ok
8 Correct 96 ms 34256 KB Ok
9 Correct 108 ms 32968 KB Ok
10 Correct 101 ms 34760 KB Ok
11 Correct 103 ms 33236 KB Ok
12 Correct 122 ms 33232 KB Ok
13 Correct 60 ms 36920 KB Ok
14 Correct 61 ms 37060 KB Ok
15 Correct 81 ms 37068 KB Ok
16 Correct 64 ms 37068 KB Ok
17 Correct 68 ms 37060 KB Ok
18 Correct 63 ms 37464 KB Ok
19 Correct 80 ms 37328 KB Ok
20 Correct 70 ms 37332 KB Ok
21 Correct 93 ms 37600 KB Ok
22 Correct 67 ms 37320 KB Ok
23 Correct 30 ms 37588 KB Ok
24 Correct 60 ms 37588 KB Ok
25 Correct 71 ms 37064 KB Ok
26 Correct 72 ms 37584 KB Ok
27 Correct 61 ms 37588 KB Ok
28 Correct 64 ms 37072 KB Ok
29 Correct 60 ms 37584 KB Ok
30 Correct 65 ms 37584 KB Ok
31 Correct 63 ms 37064 KB Ok
32 Correct 63 ms 37068 KB Ok
33 Correct 62 ms 37060 KB Ok
34 Correct 61 ms 37588 KB Ok
35 Correct 66 ms 37588 KB Ok
36 Correct 71 ms 37584 KB Ok
37 Correct 75 ms 37588 KB Ok
38 Correct 88 ms 37580 KB Ok
39 Correct 314 ms 43200 KB Ok
40 Correct 238 ms 43148 KB Ok
41 Correct 486 ms 45504 KB Ok
42 Correct 341 ms 45800 KB Ok
43 Correct 200 ms 39680 KB Ok
44 Correct 339 ms 45764 KB Ok
45 Correct 80 ms 32976 KB Ok
46 Correct 113 ms 33148 KB Ok
47 Correct 96 ms 33444 KB Ok
48 Correct 92 ms 32976 KB Ok
49 Correct 87 ms 32976 KB Ok
50 Correct 78 ms 34008 KB Ok
51 Correct 97 ms 33244 KB Ok
52 Correct 89 ms 32980 KB Ok
53 Correct 81 ms 32976 KB Ok
54 Correct 95 ms 32968 KB Ok
55 Correct 144 ms 37184 KB Ok
56 Correct 92 ms 37332 KB Ok
57 Correct 111 ms 37316 KB Ok
58 Correct 99 ms 37328 KB Ok
59 Correct 114 ms 37256 KB Ok
60 Correct 109 ms 37056 KB Ok
61 Correct 125 ms 37328 KB Ok
62 Correct 94 ms 37328 KB Ok
63 Correct 120 ms 37328 KB Ok
64 Correct 98 ms 37324 KB Ok
65 Correct 173 ms 34756 KB Ok
66 Correct 202 ms 35256 KB Ok
67 Correct 210 ms 35012 KB Ok
68 Correct 139 ms 34264 KB Ok
69 Correct 207 ms 34960 KB Ok
70 Correct 197 ms 35008 KB Ok
71 Correct 167 ms 34500 KB Ok
72 Correct 147 ms 34504 KB Ok
73 Correct 222 ms 35288 KB Ok
74 Correct 176 ms 34660 KB Ok
75 Correct 231 ms 35212 KB Ok
76 Correct 210 ms 35148 KB Ok
77 Correct 160 ms 34756 KB Ok
78 Correct 158 ms 34504 KB Ok
79 Correct 188 ms 35012 KB Ok
80 Correct 718 ms 41644 KB Ok
81 Correct 710 ms 42020 KB Ok
82 Correct 832 ms 41640 KB Ok
83 Correct 724 ms 41588 KB Ok
84 Correct 838 ms 41956 KB Ok
85 Correct 736 ms 41656 KB Ok
86 Correct 715 ms 41668 KB Ok
87 Correct 718 ms 41920 KB Ok
88 Correct 799 ms 41768 KB Ok
89 Correct 687 ms 41552 KB Ok
90 Correct 734 ms 42120 KB Ok
91 Correct 693 ms 41672 KB Ok
92 Correct 826 ms 41924 KB Ok
93 Correct 662 ms 41952 KB Ok
94 Correct 685 ms 41896 KB Ok
95 Correct 496 ms 42084 KB Ok
96 Incorrect 601 ms 45336 KB Jury has the better answer : jans = 311847, pans = 299999
97 Halted 0 ms 0 KB -