oj.uz

Submission #680757

# Submission time Handle Problem Language Result Execution time Memory
680757 2023-01-11T17:50:50 Z AndreyPavlov Nice sequence (IZhO18_sequence) C++17
15 / 100
 17 ms 13208 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);
    for (int u : t) {
        for (int v : g[u]) {
            l[u] = max(l[u], l[v] + 1);
        }
    }
    cout << len << '\n';
    for (int i = 1; i <= len; ++i) {
        cout << l[i] - l[i - 1] + (len < max(n, m) ? (len < n ? 1 : -1) : 0) << ' ';
    }
    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 7 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 9 ms 12116 KB Ok
5 Correct 7 ms 11988 KB Ok
6 Correct 9 ms 12080 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 11988 KB Ok
9 Correct 8 ms 11988 KB Ok
10 Correct 6 ms 11988 KB Ok
11 Correct 6 ms 12076 KB Ok
12 Correct 6 ms 12072 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Ok
2 Correct 6 ms 11988 KB Ok
3 Correct 7 ms 12076 KB Ok
4 Correct 8 ms 11988 KB Ok
5 Correct 7 ms 11996 KB Ok
6 Correct 11 ms 12240 KB Ok
7 Correct 14 ms 13092 KB Ok
8 Correct 11 ms 12556 KB Ok
9 Correct 17 ms 13208 KB Ok
10 Correct 11 ms 12756 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB Ok
2 Correct 6 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 6 ms 12052 KB Ok
5 Incorrect 7 ms 11988 KB All the numbers must be nonzero
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11988 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 9 ms 12116 KB Ok
5 Correct 7 ms 11988 KB Ok
6 Correct 9 ms 12080 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 11988 KB Ok
9 Correct 8 ms 11988 KB Ok
10 Correct 6 ms 11988 KB Ok
11 Correct 6 ms 12076 KB Ok
12 Correct 6 ms 12072 KB Ok
13 Correct 8 ms 11988 KB Ok
14 Correct 6 ms 11988 KB Ok
15 Correct 6 ms 11988 KB Ok
16 Correct 6 ms 12052 KB Ok
17 Incorrect 7 ms 11988 KB All the numbers must be nonzero
18 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 9 ms 12116 KB Ok
5 Correct 7 ms 11988 KB Ok
6 Correct 9 ms 12080 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 11988 KB Ok
9 Correct 8 ms 11988 KB Ok
10 Correct 6 ms 11988 KB Ok
11 Correct 6 ms 12076 KB Ok
12 Correct 6 ms 12072 KB Ok
13 Correct 6 ms 11988 KB Ok
14 Correct 6 ms 11988 KB Ok
15 Correct 7 ms 12076 KB Ok
16 Correct 8 ms 11988 KB Ok
17 Correct 7 ms 11996 KB Ok
18 Correct 11 ms 12240 KB Ok
19 Correct 14 ms 13092 KB Ok
20 Correct 11 ms 12556 KB Ok
21 Correct 17 ms 13208 KB Ok
22 Correct 11 ms 12756 KB Ok
23 Correct 8 ms 11988 KB Ok
24 Correct 6 ms 11988 KB Ok
25 Correct 6 ms 11988 KB Ok
26 Correct 6 ms 12052 KB Ok
27 Incorrect 7 ms 11988 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Ok
2 Correct 7 ms 11988 KB Ok
3 Correct 6 ms 11988 KB Ok
4 Correct 9 ms 12116 KB Ok
5 Correct 7 ms 11988 KB Ok
6 Correct 9 ms 12080 KB Ok
7 Correct 8 ms 11988 KB Ok
8 Correct 6 ms 11988 KB Ok
9 Correct 8 ms 11988 KB Ok
10 Correct 6 ms 11988 KB Ok
11 Correct 6 ms 12076 KB Ok
12 Correct 6 ms 12072 KB Ok
13 Correct 6 ms 11988 KB Ok
14 Correct 6 ms 11988 KB Ok
15 Correct 7 ms 12076 KB Ok
16 Correct 8 ms 11988 KB Ok
17 Correct 7 ms 11996 KB Ok
18 Correct 11 ms 12240 KB Ok
19 Correct 14 ms 13092 KB Ok
20 Correct 11 ms 12556 KB Ok
21 Correct 17 ms 13208 KB Ok
22 Correct 11 ms 12756 KB Ok
23 Correct 8 ms 11988 KB Ok
24 Correct 6 ms 11988 KB Ok
25 Correct 6 ms 11988 KB Ok
26 Correct 6 ms 12052 KB Ok
27 Incorrect 7 ms 11988 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -