oj.uz

Submission #680760

# Submission time Handle Problem Language Result Execution time Memory
680760 2023-01-11T17:59:19 Z AndreyPavlov Nice sequence (IZhO18_sequence) C++17
100 / 100
 1169 ms 82164 KB 
/* Includes */
#include <bits/stdc++.h>

/* Using libraries */
using namespace std;

/* Defines */
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ld long double
#define pb push_back
#define sz(a) (int)a.size()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pii pair <int, int>
#define vec pt
#define vc vector
#define all(a) a.begin(), a.end()
#define int long long

const int N = 5e5;
vc <int> g[N], t;
int used[N];

void dfs(int u) {
    used[u] = 1;
    for (int v: g[u]) {
        if (!used[v])
            dfs(v);
    }
    t.pb(u);
}

void solve () {
    int n, m;
    cin >> n >> m;
    int len = n + m - 1 - __gcd(n, m);
    for (int i = 0; i <= len; ++i)
        g[i].clear(), used[i] = 0;
    t.clear();
    for (int i = 0; i <= len; ++i) {
        if (i >= m)
            g[i].pb(i - m);
        if (i >= n)
            g[i - n].pb(i);
    }
    for (int i = 0; i <= len; ++i) {
        if (!used[i])
            dfs(i);
    }
    vc <int> l(len + 1);
    int cnt = 0;
    for (int u : t) {
        l[u] = cnt++;
    }
    cout << len << '\n';
    vc <int> p(len);
    for (int i = 1; i <= len; ++i) {
        p[i - 1] = l[i] - l[i - 1];
    }
    for (int i = 0; i < len; ++i) {
        cout << p[i] << ' ';
    }
    cout << '\n';
}

/* Starting and precalcing */
signed main() {
    fast;
    cout << fixed << setprecision(12);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 11988 KB Ok
5 Correct 8 ms 11988 KB Ok
6 Correct 9 ms 11988 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 12036 KB Ok
9 Correct 7 ms 11988 KB Ok
10 Correct 7 ms 11988 KB Ok
11 Correct 6 ms 11988 KB Ok
12 Correct 6 ms 11988 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Ok
2 Correct 6 ms 12032 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 7 ms 11988 KB Ok
5 Correct 6 ms 11988 KB Ok
6 Correct 7 ms 12244 KB Ok
7 Correct 13 ms 13268 KB Ok
8 Correct 10 ms 12628 KB Ok
9 Correct 17 ms 13340 KB Ok
10 Correct 11 ms 12756 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 6 ms 12032 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 11988 KB Ok
5 Correct 6 ms 11988 KB Ok
6 Correct 6 ms 12000 KB Ok
7 Correct 7 ms 12116 KB Ok
8 Correct 6 ms 11988 KB Ok
9 Correct 6 ms 11988 KB Ok
10 Correct 6 ms 12116 KB Ok
11 Correct 8 ms 11996 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Ok
2 Correct 8 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 7 ms 11996 KB Ok
5 Correct 6 ms 11988 KB Ok
6 Correct 87 ms 28412 KB Ok
7 Correct 81 ms 34936 KB Ok
8 Correct 144 ms 38808 KB Ok
9 Correct 114 ms 36260 KB Ok
10 Correct 62 ms 24172 KB Ok
11 Correct 106 ms 32236 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 11988 KB Ok
5 Correct 8 ms 11988 KB Ok
6 Correct 9 ms 11988 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 12036 KB Ok
9 Correct 7 ms 11988 KB Ok
10 Correct 7 ms 11988 KB Ok
11 Correct 6 ms 11988 KB Ok
12 Correct 6 ms 11988 KB Ok
13 Correct 6 ms 11988 KB Ok
14 Correct 6 ms 12032 KB Ok
15 Correct 6 ms 11988 KB Ok
16 Correct 6 ms 11988 KB Ok
17 Correct 6 ms 11988 KB Ok
18 Correct 6 ms 12000 KB Ok
19 Correct 7 ms 12116 KB Ok
20 Correct 6 ms 11988 KB Ok
21 Correct 6 ms 11988 KB Ok
22 Correct 6 ms 12116 KB Ok
23 Correct 8 ms 11996 KB Ok
24 Correct 11 ms 12204 KB Ok
25 Correct 8 ms 12244 KB Ok
26 Correct 10 ms 12244 KB Ok
27 Correct 8 ms 12320 KB Ok
28 Correct 8 ms 12200 KB Ok
29 Correct 8 ms 12244 KB Ok
30 Correct 8 ms 12128 KB Ok
31 Correct 9 ms 12244 KB Ok
32 Correct 8 ms 12244 KB Ok
33 Correct 8 ms 12196 KB Ok
34 Correct 9 ms 12492 KB Ok
35 Correct 9 ms 12580 KB Ok
36 Correct 9 ms 12500 KB Ok
37 Correct 10 ms 12500 KB Ok
38 Correct 11 ms 12580 KB Ok
39 Correct 12 ms 12500 KB Ok
40 Correct 10 ms 12628 KB Ok
41 Correct 10 ms 12500 KB Ok
42 Correct 10 ms 12512 KB Ok
43 Correct 9 ms 12628 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 11988 KB Ok
5 Correct 8 ms 11988 KB Ok
6 Correct 9 ms 11988 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 12036 KB Ok
9 Correct 7 ms 11988 KB Ok
10 Correct 7 ms 11988 KB Ok
11 Correct 6 ms 11988 KB Ok
12 Correct 6 ms 11988 KB Ok
13 Correct 7 ms 11988 KB Ok
14 Correct 6 ms 12032 KB Ok
15 Correct 6 ms 11988 KB Ok
16 Correct 7 ms 11988 KB Ok
17 Correct 6 ms 11988 KB Ok
18 Correct 7 ms 12244 KB Ok
19 Correct 13 ms 13268 KB Ok
20 Correct 10 ms 12628 KB Ok
21 Correct 17 ms 13340 KB Ok
22 Correct 11 ms 12756 KB Ok
23 Correct 6 ms 11988 KB Ok
24 Correct 6 ms 12032 KB Ok
25 Correct 6 ms 11988 KB Ok
26 Correct 6 ms 11988 KB Ok
27 Correct 6 ms 11988 KB Ok
28 Correct 6 ms 12000 KB Ok
29 Correct 7 ms 12116 KB Ok
30 Correct 6 ms 11988 KB Ok
31 Correct 6 ms 11988 KB Ok
32 Correct 6 ms 12116 KB Ok
33 Correct 8 ms 11996 KB Ok
34 Correct 11 ms 12204 KB Ok
35 Correct 8 ms 12244 KB Ok
36 Correct 10 ms 12244 KB Ok
37 Correct 8 ms 12320 KB Ok
38 Correct 8 ms 12200 KB Ok
39 Correct 8 ms 12244 KB Ok
40 Correct 8 ms 12128 KB Ok
41 Correct 9 ms 12244 KB Ok
42 Correct 8 ms 12244 KB Ok
43 Correct 8 ms 12196 KB Ok
44 Correct 9 ms 12492 KB Ok
45 Correct 9 ms 12580 KB Ok
46 Correct 9 ms 12500 KB Ok
47 Correct 10 ms 12500 KB Ok
48 Correct 11 ms 12580 KB Ok
49 Correct 12 ms 12500 KB Ok
50 Correct 10 ms 12628 KB Ok
51 Correct 10 ms 12500 KB Ok
52 Correct 10 ms 12512 KB Ok
53 Correct 9 ms 12628 KB Ok
54 Correct 66 ms 19244 KB Ok
55 Correct 78 ms 19628 KB Ok
56 Correct 76 ms 19712 KB Ok
57 Correct 58 ms 18464 KB Ok
58 Correct 68 ms 18988 KB Ok
59 Correct 63 ms 18624 KB Ok
60 Correct 63 ms 18208 KB Ok
61 Correct 58 ms 18748 KB Ok
62 Correct 73 ms 19192 KB Ok
63 Correct 62 ms 18668 KB Ok
64 Correct 75 ms 19516 KB Ok
65 Correct 73 ms 19296 KB Ok
66 Correct 60 ms 18964 KB Ok
67 Correct 56 ms 18760 KB Ok
68 Correct 64 ms 19232 KB Ok
69 Correct 185 ms 28752 KB Ok
70 Correct 190 ms 29436 KB Ok
71 Correct 164 ms 28752 KB Ok
72 Correct 155 ms 28756 KB Ok
73 Correct 172 ms 28064 KB Ok
74 Correct 189 ms 27844 KB Ok
75 Correct 166 ms 28068 KB Ok
76 Correct 161 ms 29052 KB Ok
77 Correct 154 ms 27500 KB Ok
78 Correct 173 ms 27696 KB Ok
79 Correct 154 ms 28556 KB Ok
80 Correct 168 ms 28688 KB Ok
81 Correct 161 ms 28028 KB Ok
82 Correct 175 ms 28404 KB Ok
83 Correct 166 ms 28044 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 11988 KB Ok
5 Correct 8 ms 11988 KB Ok
6 Correct 9 ms 11988 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 12036 KB Ok
9 Correct 7 ms 11988 KB Ok
10 Correct 7 ms 11988 KB Ok
11 Correct 6 ms 11988 KB Ok
12 Correct 6 ms 11988 KB Ok
13 Correct 7 ms 11988 KB Ok
14 Correct 6 ms 12032 KB Ok
15 Correct 6 ms 11988 KB Ok
16 Correct 7 ms 11988 KB Ok
17 Correct 6 ms 11988 KB Ok
18 Correct 7 ms 12244 KB Ok
19 Correct 13 ms 13268 KB Ok
20 Correct 10 ms 12628 KB Ok
21 Correct 17 ms 13340 KB Ok
22 Correct 11 ms 12756 KB Ok
23 Correct 6 ms 11988 KB Ok
24 Correct 6 ms 12032 KB Ok
25 Correct 6 ms 11988 KB Ok
26 Correct 6 ms 11988 KB Ok
27 Correct 6 ms 11988 KB Ok
28 Correct 6 ms 12000 KB Ok
29 Correct 7 ms 12116 KB Ok
30 Correct 6 ms 11988 KB Ok
31 Correct 6 ms 11988 KB Ok
32 Correct 6 ms 12116 KB Ok
33 Correct 8 ms 11996 KB Ok
34 Correct 7 ms 11988 KB Ok
35 Correct 8 ms 11988 KB Ok
36 Correct 6 ms 11988 KB Ok
37 Correct 7 ms 11996 KB Ok
38 Correct 6 ms 11988 KB Ok
39 Correct 87 ms 28412 KB Ok
40 Correct 81 ms 34936 KB Ok
41 Correct 144 ms 38808 KB Ok
42 Correct 114 ms 36260 KB Ok
43 Correct 62 ms 24172 KB Ok
44 Correct 106 ms 32236 KB Ok
45 Correct 11 ms 12204 KB Ok
46 Correct 8 ms 12244 KB Ok
47 Correct 10 ms 12244 KB Ok
48 Correct 8 ms 12320 KB Ok
49 Correct 8 ms 12200 KB Ok
50 Correct 8 ms 12244 KB Ok
51 Correct 8 ms 12128 KB Ok
52 Correct 9 ms 12244 KB Ok
53 Correct 8 ms 12244 KB Ok
54 Correct 8 ms 12196 KB Ok
55 Correct 9 ms 12492 KB Ok
56 Correct 9 ms 12580 KB Ok
57 Correct 9 ms 12500 KB Ok
58 Correct 10 ms 12500 KB Ok
59 Correct 11 ms 12580 KB Ok
60 Correct 12 ms 12500 KB Ok
61 Correct 10 ms 12628 KB Ok
62 Correct 10 ms 12500 KB Ok
63 Correct 10 ms 12512 KB Ok
64 Correct 9 ms 12628 KB Ok
65 Correct 66 ms 19244 KB Ok
66 Correct 78 ms 19628 KB Ok
67 Correct 76 ms 19712 KB Ok
68 Correct 58 ms 18464 KB Ok
69 Correct 68 ms 18988 KB Ok
70 Correct 63 ms 18624 KB Ok
71 Correct 63 ms 18208 KB Ok
72 Correct 58 ms 18748 KB Ok
73 Correct 73 ms 19192 KB Ok
74 Correct 62 ms 18668 KB Ok
75 Correct 75 ms 19516 KB Ok
76 Correct 73 ms 19296 KB Ok
77 Correct 60 ms 18964 KB Ok
78 Correct 56 ms 18760 KB Ok
79 Correct 64 ms 19232 KB Ok
80 Correct 185 ms 28752 KB Ok
81 Correct 190 ms 29436 KB Ok
82 Correct 164 ms 28752 KB Ok
83 Correct 155 ms 28756 KB Ok
84 Correct 172 ms 28064 KB Ok
85 Correct 189 ms 27844 KB Ok
86 Correct 166 ms 28068 KB Ok
87 Correct 161 ms 29052 KB Ok
88 Correct 154 ms 27500 KB Ok
89 Correct 173 ms 27696 KB Ok
90 Correct 154 ms 28556 KB Ok
91 Correct 168 ms 28688 KB Ok
92 Correct 161 ms 28028 KB Ok
93 Correct 175 ms 28404 KB Ok
94 Correct 166 ms 28044 KB Ok
95 Correct 160 ms 30888 KB Ok
96 Correct 236 ms 41576 KB Ok
97 Correct 208 ms 34380 KB Ok
98 Correct 158 ms 33736 KB Ok
99 Correct 195 ms 33952 KB Ok
100 Correct 192 ms 33368 KB Ok
101 Correct 198 ms 37276 KB Ok
102 Correct 201 ms 36124 KB Ok
103 Correct 193 ms 36356 KB Ok
104 Correct 229 ms 38692 KB Ok
105 Correct 228 ms 40900 KB Ok
106 Correct 208 ms 39632 KB Ok
107 Correct 206 ms 37792 KB Ok
108 Correct 261 ms 40052 KB Ok
109 Correct 225 ms 40672 KB Ok
110 Correct 927 ms 79432 KB Ok
111 Correct 1040 ms 81656 KB Ok
112 Correct 1010 ms 77660 KB Ok
113 Correct 1006 ms 82164 KB Ok
114 Correct 984 ms 81804 KB Ok
115 Correct 996 ms 79020 KB Ok
116 Correct 1006 ms 81788 KB Ok
117 Correct 922 ms 81172 KB Ok
118 Correct 1064 ms 81696 KB Ok
119 Correct 941 ms 80600 KB Ok
120 Correct 925 ms 80476 KB Ok
121 Correct 1058 ms 80340 KB Ok
122 Correct 924 ms 79708 KB Ok
123 Correct 1169 ms 82100 KB Ok
124 Correct 892 ms 75592 KB Ok
125 Correct 366 ms 65892 KB Ok