oj.uz

Submission #493142

# Submission time Handle Problem Language Result Execution time Memory
493142 2021-12-10T06:37:43 Z baokhue232005 Nice sequence (IZhO18_sequence) C++17
100 / 100
 1196 ms 59240 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 500005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;
int m;

vector<int> vc[maxN];
int chim[maxN];
int track = 0;
int cnt[maxN];
int l, r;
int stk[maxN];
int pinn;

bool solve(int rang){
    track = 0;
    pinn = 0;
    memset(cnt, 0, sizeof(cnt));
    for1(i, 0, rang){
        if(i >= m) ++cnt[i - m];
        if(i >= n) ++cnt[i];
    }
    for1(i, 0, rang) if(!cnt[i]) stk[++pinn] = i;
    while(pinn){
        x = stk[pinn--];
        chim[track++] = x;
        for(int cc : vc[x]){
            --cnt[cc]; if(!cnt[cc]) stk[++pinn] = cc;
        }
    }
    if(track <= rang) return 0;
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int o; cin >> o; while(o--){
        cin >> n >> m;
        l = max(n, m) - 1; r = n + m;
        for1(i, 0, r){
            vc[i].clear();
            if(i >= m) vc[i].pb(i - m);
            if(i >= n) vc[i - n].pb(i);
        }
        l = m + n - __gcd(m, n) - 1;
        solve(l);
        x = maxN;
        int cc;
        for1(i, 0, track - 1){
            if(chim[i] == 0) x = 0; else --x;
            a[chim[i]] = x;
        }
        cout << l << endl;
        for1(i, 1, l) cout << a[i] - a[i - 1] << " ";
        cout << endl;
    }
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:72:13: warning: unused variable 'cc' [-Wunused-variable]
   72 |         int cc;
      |             ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14028 KB Ok
2 Correct 7 ms 13984 KB Ok
3 Correct 8 ms 14028 KB Ok
4 Correct 7 ms 13992 KB Ok
5 Correct 7 ms 14028 KB Ok
6 Correct 7 ms 13988 KB Ok
7 Correct 8 ms 14028 KB Ok
8 Correct 7 ms 14028 KB Ok
9 Correct 8 ms 14028 KB Ok
10 Correct 7 ms 14028 KB Ok
11 Correct 8 ms 14028 KB Ok
12 Correct 7 ms 13988 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13988 KB Ok
2 Correct 8 ms 14028 KB Ok
3 Correct 8 ms 13988 KB Ok
4 Correct 8 ms 14028 KB Ok
5 Correct 8 ms 14028 KB Ok
6 Correct 9 ms 14220 KB Ok
7 Correct 20 ms 14924 KB Ok
8 Correct 11 ms 14412 KB Ok
9 Correct 22 ms 15080 KB Ok
10 Correct 13 ms 14624 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14028 KB Ok
2 Correct 7 ms 13948 KB Ok
3 Correct 7 ms 13980 KB Ok
4 Correct 8 ms 13916 KB Ok
5 Correct 8 ms 14028 KB Ok
6 Correct 8 ms 14028 KB Ok
7 Correct 7 ms 14028 KB Ok
8 Correct 7 ms 14028 KB Ok
9 Correct 7 ms 14028 KB Ok
10 Correct 7 ms 14028 KB Ok
11 Correct 8 ms 13920 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13988 KB Ok
2 Correct 7 ms 14028 KB Ok
3 Correct 8 ms 14028 KB Ok
4 Correct 7 ms 13944 KB Ok
5 Correct 8 ms 13988 KB Ok
6 Correct 103 ms 25200 KB Ok
7 Correct 78 ms 23900 KB Ok
8 Correct 149 ms 28356 KB Ok
9 Correct 119 ms 26948 KB Ok
10 Correct 71 ms 21472 KB Ok
11 Correct 114 ms 27004 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14028 KB Ok
2 Correct 7 ms 13984 KB Ok
3 Correct 8 ms 14028 KB Ok
4 Correct 7 ms 13992 KB Ok
5 Correct 7 ms 14028 KB Ok
6 Correct 7 ms 13988 KB Ok
7 Correct 8 ms 14028 KB Ok
8 Correct 7 ms 14028 KB Ok
9 Correct 8 ms 14028 KB Ok
10 Correct 7 ms 14028 KB Ok
11 Correct 8 ms 14028 KB Ok
12 Correct 7 ms 13988 KB Ok
13 Correct 8 ms 14028 KB Ok
14 Correct 7 ms 13948 KB Ok
15 Correct 7 ms 13980 KB Ok
16 Correct 8 ms 13916 KB Ok
17 Correct 8 ms 14028 KB Ok
18 Correct 8 ms 14028 KB Ok
19 Correct 7 ms 14028 KB Ok
20 Correct 7 ms 14028 KB Ok
21 Correct 7 ms 14028 KB Ok
22 Correct 7 ms 14028 KB Ok
23 Correct 8 ms 13920 KB Ok
24 Correct 9 ms 14156 KB Ok
25 Correct 10 ms 14284 KB Ok
26 Correct 9 ms 14184 KB Ok
27 Correct 10 ms 14136 KB Ok
28 Correct 9 ms 14168 KB Ok
29 Correct 10 ms 14156 KB Ok
30 Correct 8 ms 14156 KB Ok
31 Correct 10 ms 14156 KB Ok
32 Correct 9 ms 14156 KB Ok
33 Correct 9 ms 14156 KB Ok
34 Correct 11 ms 14284 KB Ok
35 Correct 12 ms 14376 KB Ok
36 Correct 11 ms 14284 KB Ok
37 Correct 11 ms 14284 KB Ok
38 Correct 13 ms 14284 KB Ok
39 Correct 11 ms 14336 KB Ok
40 Correct 11 ms 14372 KB Ok
41 Correct 11 ms 14284 KB Ok
42 Correct 12 ms 14284 KB Ok
43 Correct 12 ms 14372 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14028 KB Ok
2 Correct 7 ms 13984 KB Ok
3 Correct 8 ms 14028 KB Ok
4 Correct 7 ms 13992 KB Ok
5 Correct 7 ms 14028 KB Ok
6 Correct 7 ms 13988 KB Ok
7 Correct 8 ms 14028 KB Ok
8 Correct 7 ms 14028 KB Ok
9 Correct 8 ms 14028 KB Ok
10 Correct 7 ms 14028 KB Ok
11 Correct 8 ms 14028 KB Ok
12 Correct 7 ms 13988 KB Ok
13 Correct 10 ms 13988 KB Ok
14 Correct 8 ms 14028 KB Ok
15 Correct 8 ms 13988 KB Ok
16 Correct 8 ms 14028 KB Ok
17 Correct 8 ms 14028 KB Ok
18 Correct 9 ms 14220 KB Ok
19 Correct 20 ms 14924 KB Ok
20 Correct 11 ms 14412 KB Ok
21 Correct 22 ms 15080 KB Ok
22 Correct 13 ms 14624 KB Ok
23 Correct 8 ms 14028 KB Ok
24 Correct 7 ms 13948 KB Ok
25 Correct 7 ms 13980 KB Ok
26 Correct 8 ms 13916 KB Ok
27 Correct 8 ms 14028 KB Ok
28 Correct 8 ms 14028 KB Ok
29 Correct 7 ms 14028 KB Ok
30 Correct 7 ms 14028 KB Ok
31 Correct 7 ms 14028 KB Ok
32 Correct 7 ms 14028 KB Ok
33 Correct 8 ms 13920 KB Ok
34 Correct 9 ms 14156 KB Ok
35 Correct 10 ms 14284 KB Ok
36 Correct 9 ms 14184 KB Ok
37 Correct 10 ms 14136 KB Ok
38 Correct 9 ms 14168 KB Ok
39 Correct 10 ms 14156 KB Ok
40 Correct 8 ms 14156 KB Ok
41 Correct 10 ms 14156 KB Ok
42 Correct 9 ms 14156 KB Ok
43 Correct 9 ms 14156 KB Ok
44 Correct 11 ms 14284 KB Ok
45 Correct 12 ms 14376 KB Ok
46 Correct 11 ms 14284 KB Ok
47 Correct 11 ms 14284 KB Ok
48 Correct 13 ms 14284 KB Ok
49 Correct 11 ms 14336 KB Ok
50 Correct 11 ms 14372 KB Ok
51 Correct 11 ms 14284 KB Ok
52 Correct 12 ms 14284 KB Ok
53 Correct 12 ms 14372 KB Ok
54 Correct 86 ms 19652 KB Ok
55 Correct 104 ms 20112 KB Ok
56 Correct 95 ms 20168 KB Ok
57 Correct 69 ms 19012 KB Ok
58 Correct 86 ms 19728 KB Ok
59 Correct 81 ms 19684 KB Ok
60 Correct 71 ms 19440 KB Ok
61 Correct 85 ms 19328 KB Ok
62 Correct 96 ms 19776 KB Ok
63 Correct 81 ms 19324 KB Ok
64 Correct 94 ms 19940 KB Ok
65 Correct 97 ms 19872 KB Ok
66 Correct 85 ms 19524 KB Ok
67 Correct 68 ms 19140 KB Ok
68 Correct 77 ms 19644 KB Ok
69 Correct 172 ms 24388 KB Ok
70 Correct 161 ms 25028 KB Ok
71 Correct 157 ms 24748 KB Ok
72 Correct 158 ms 24220 KB Ok
73 Correct 157 ms 24652 KB Ok
74 Correct 188 ms 24440 KB Ok
75 Correct 194 ms 24260 KB Ok
76 Correct 176 ms 24648 KB Ok
77 Correct 168 ms 24320 KB Ok
78 Correct 171 ms 24368 KB Ok
79 Correct 174 ms 24820 KB Ok
80 Correct 186 ms 24760 KB Ok
81 Correct 185 ms 24740 KB Ok
82 Correct 205 ms 24640 KB Ok
83 Correct 193 ms 24532 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14028 KB Ok
2 Correct 7 ms 13984 KB Ok
3 Correct 8 ms 14028 KB Ok
4 Correct 7 ms 13992 KB Ok
5 Correct 7 ms 14028 KB Ok
6 Correct 7 ms 13988 KB Ok
7 Correct 8 ms 14028 KB Ok
8 Correct 7 ms 14028 KB Ok
9 Correct 8 ms 14028 KB Ok
10 Correct 7 ms 14028 KB Ok
11 Correct 8 ms 14028 KB Ok
12 Correct 7 ms 13988 KB Ok
13 Correct 10 ms 13988 KB Ok
14 Correct 8 ms 14028 KB Ok
15 Correct 8 ms 13988 KB Ok
16 Correct 8 ms 14028 KB Ok
17 Correct 8 ms 14028 KB Ok
18 Correct 9 ms 14220 KB Ok
19 Correct 20 ms 14924 KB Ok
20 Correct 11 ms 14412 KB Ok
21 Correct 22 ms 15080 KB Ok
22 Correct 13 ms 14624 KB Ok
23 Correct 8 ms 14028 KB Ok
24 Correct 7 ms 13948 KB Ok
25 Correct 7 ms 13980 KB Ok
26 Correct 8 ms 13916 KB Ok
27 Correct 8 ms 14028 KB Ok
28 Correct 8 ms 14028 KB Ok
29 Correct 7 ms 14028 KB Ok
30 Correct 7 ms 14028 KB Ok
31 Correct 7 ms 14028 KB Ok
32 Correct 7 ms 14028 KB Ok
33 Correct 8 ms 13920 KB Ok
34 Correct 7 ms 13988 KB Ok
35 Correct 7 ms 14028 KB Ok
36 Correct 8 ms 14028 KB Ok
37 Correct 7 ms 13944 KB Ok
38 Correct 8 ms 13988 KB Ok
39 Correct 103 ms 25200 KB Ok
40 Correct 78 ms 23900 KB Ok
41 Correct 149 ms 28356 KB Ok
42 Correct 119 ms 26948 KB Ok
43 Correct 71 ms 21472 KB Ok
44 Correct 114 ms 27004 KB Ok
45 Correct 9 ms 14156 KB Ok
46 Correct 10 ms 14284 KB Ok
47 Correct 9 ms 14184 KB Ok
48 Correct 10 ms 14136 KB Ok
49 Correct 9 ms 14168 KB Ok
50 Correct 10 ms 14156 KB Ok
51 Correct 8 ms 14156 KB Ok
52 Correct 10 ms 14156 KB Ok
53 Correct 9 ms 14156 KB Ok
54 Correct 9 ms 14156 KB Ok
55 Correct 11 ms 14284 KB Ok
56 Correct 12 ms 14376 KB Ok
57 Correct 11 ms 14284 KB Ok
58 Correct 11 ms 14284 KB Ok
59 Correct 13 ms 14284 KB Ok
60 Correct 11 ms 14336 KB Ok
61 Correct 11 ms 14372 KB Ok
62 Correct 11 ms 14284 KB Ok
63 Correct 12 ms 14284 KB Ok
64 Correct 12 ms 14372 KB Ok
65 Correct 86 ms 19652 KB Ok
66 Correct 104 ms 20112 KB Ok
67 Correct 95 ms 20168 KB Ok
68 Correct 69 ms 19012 KB Ok
69 Correct 86 ms 19728 KB Ok
70 Correct 81 ms 19684 KB Ok
71 Correct 71 ms 19440 KB Ok
72 Correct 85 ms 19328 KB Ok
73 Correct 96 ms 19776 KB Ok
74 Correct 81 ms 19324 KB Ok
75 Correct 94 ms 19940 KB Ok
76 Correct 97 ms 19872 KB Ok
77 Correct 85 ms 19524 KB Ok
78 Correct 68 ms 19140 KB Ok
79 Correct 77 ms 19644 KB Ok
80 Correct 172 ms 24388 KB Ok
81 Correct 161 ms 25028 KB Ok
82 Correct 157 ms 24748 KB Ok
83 Correct 158 ms 24220 KB Ok
84 Correct 157 ms 24652 KB Ok
85 Correct 188 ms 24440 KB Ok
86 Correct 194 ms 24260 KB Ok
87 Correct 176 ms 24648 KB Ok
88 Correct 168 ms 24320 KB Ok
89 Correct 171 ms 24368 KB Ok
90 Correct 174 ms 24820 KB Ok
91 Correct 186 ms 24760 KB Ok
92 Correct 185 ms 24740 KB Ok
93 Correct 205 ms 24640 KB Ok
94 Correct 193 ms 24532 KB Ok
95 Correct 230 ms 30212 KB Ok
96 Correct 307 ms 35572 KB Ok
97 Correct 270 ms 32560 KB Ok
98 Correct 204 ms 31888 KB Ok
99 Correct 239 ms 32028 KB Ok
100 Correct 241 ms 31700 KB Ok
101 Correct 258 ms 34972 KB Ok
102 Correct 270 ms 34916 KB Ok
103 Correct 280 ms 33600 KB Ok
104 Correct 307 ms 36308 KB Ok
105 Correct 277 ms 34964 KB Ok
106 Correct 269 ms 34504 KB Ok
107 Correct 253 ms 34748 KB Ok
108 Correct 308 ms 34252 KB Ok
109 Correct 272 ms 35236 KB Ok
110 Correct 973 ms 56272 KB Ok
111 Correct 942 ms 57520 KB Ok
112 Correct 977 ms 58776 KB Ok
113 Correct 931 ms 56968 KB Ok
114 Correct 923 ms 59240 KB Ok
115 Correct 994 ms 57824 KB Ok
116 Correct 1006 ms 58564 KB Ok
117 Correct 879 ms 56700 KB Ok
118 Correct 1132 ms 58456 KB Ok
119 Correct 954 ms 56432 KB Ok
120 Correct 972 ms 56964 KB Ok
121 Correct 1175 ms 57292 KB Ok
122 Correct 1012 ms 57844 KB Ok
123 Correct 1196 ms 58148 KB Ok
124 Correct 1057 ms 57900 KB Ok
125 Correct 375 ms 39648 KB Ok