oj.uz

Submission #689392

# Submission time Handle Problem Language Result Execution time Memory
689392 2023-01-28T11:47:44 Z gesgha Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 47828 KB 
#include <bits/stdc++.h>

#define fr(x, l, r) for (int x = l; x <= r; x++)
#define rf(x, l, r) for (int x = l; x >= r; x--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pw(x) (ll(1) << ull(x))
#define all(x) (x).begin(), x.end()
#define sz(x) (int)x.size()
#define mt make_tuple

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;

template <typename T>
using ve = vector<T>;

template <typename T>
bool umn(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T>
bool umx(T& a, T b) {return a < b ? a = b, 1 : 0;}

const ll OO = 1e18;
const int oo = 1e9;
const int mod = 1e9 + 7;
const int P = 29;
const ld eps = 0.00000001;
const int N = 1e6 + 10;
const bool TEST = 1;

void precalc() {}

int G[N][10];
int sz[N];
int a[N];
int sz_A;
bool vis[N];

void dfs(int v) {
    vis[v] = 1;
    fr(i, 0, sz[v] - 1) if (!vis[G[v][i]]) dfs(G[v][i]);
    a[sz_A++] = v;
}

int cnt(int v) {
    vis[v] = 1;
    int res = 1;
    fr(i, 0, sz[v] - 1) if (!vis[G[v][i]]) {
        return 2;
        res += cnt(G[v][i]);
    }
    return res;
}

bool can(int n, int m, int k) {
    fr(i, 0, k) sz[i] = 0;
    sz_A = 0;
    fr(i, 0, k) vis[i] = 0;
    fr(i, 1, k) {
        if (i + n - 1 <= k) G[i + n - 1][sz[i + n - 1]++] = (i - 1);
        if (i + m - 1 <= k) G[i - 1][sz[i - 1]++] = (i + m - 1);
    }
    fr(i, 0, k) if (!vis[i]) dfs(i);
    fill(vis, vis + k + 1, 0);
    fr (i, 0, k) {
        int x = cnt(a[i]);
        if (x > 1) return 0;
    }
    return 1;
}
int pr[N];
int A[N];

void solve(int TST) {
    int n, m;
    cin >> n >> m;

    int l = max(n, m) - 1;
    int r = 4 * max(n, m);

    while(l < r) {
        int tm = (l + r + 1) >> 1;
        if (can(n, m, tm)) l = tm;
        else r = tm - 1;
    }

    fr(i, 0, l) sz[i] = 0;
    sz_A = 0;

    fr(i, 0, l) vis[i] = 0;
    fr(i, 1, l) {
        if (i + n - 1 <= l) G[i + n - 1][sz[i + n - 1]++] = (i - 1);
        if (i + m - 1 <= l) G[i - 1][sz[i - 1]++] = (i + m - 1);
    }
    fr(i, 0, l) if (!vis[i]) dfs(i);
    reverse(a, a + sz_A);

    int cnt = 0;
    fr (i, 0, sz_A - 1) pr[a[i]] = cnt++;

    fr(i, 1, l) A[i] = pr[i] - pr[i - 1];

    cout << l << endl;
    fr(i, 1, l) cout << A[i] << ' ';
    cout << endl;
}


int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q = 1;
    if (TEST) cin >> q;
    precalc();
    for (int z = 1; z <= q; z++) {
        solve(z);
    }
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 328 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 328 KB Ok
6 Correct 6 ms 880 KB Ok
7 Correct 27 ms 3004 KB Ok
8 Correct 13 ms 1580 KB Ok
9 Correct 35 ms 3516 KB Ok
10 Correct 19 ms 2124 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 292 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Ok
2 Correct 1 ms 344 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 358 ms 24568 KB Ok
7 Correct 292 ms 28108 KB Ok
8 Correct 642 ms 30048 KB Ok
9 Correct 460 ms 27868 KB Ok
10 Correct 243 ms 16916 KB Ok
11 Correct 505 ms 30772 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 284 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 1 ms 328 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 328 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 292 KB Ok
15 Correct 1 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 1 ms 340 KB Ok
19 Correct 0 ms 340 KB Ok
20 Correct 0 ms 340 KB Ok
21 Correct 0 ms 340 KB Ok
22 Correct 0 ms 340 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 5 ms 596 KB Ok
25 Correct 5 ms 588 KB Ok
26 Correct 5 ms 596 KB Ok
27 Correct 5 ms 596 KB Ok
28 Correct 4 ms 608 KB Ok
29 Correct 4 ms 724 KB Ok
30 Correct 4 ms 592 KB Ok
31 Correct 5 ms 596 KB Ok
32 Correct 5 ms 596 KB Ok
33 Correct 5 ms 580 KB Ok
34 Correct 11 ms 900 KB Ok
35 Correct 11 ms 972 KB Ok
36 Correct 11 ms 984 KB Ok
37 Correct 10 ms 964 KB Ok
38 Correct 10 ms 980 KB Ok
39 Correct 10 ms 980 KB Ok
40 Correct 11 ms 980 KB Ok
41 Correct 11 ms 980 KB Ok
42 Correct 11 ms 916 KB Ok
43 Correct 11 ms 1036 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 284 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 1 ms 328 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 328 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 1 ms 328 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 328 KB Ok
18 Correct 6 ms 880 KB Ok
19 Correct 27 ms 3004 KB Ok
20 Correct 13 ms 1580 KB Ok
21 Correct 35 ms 3516 KB Ok
22 Correct 19 ms 2124 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 292 KB Ok
25 Correct 1 ms 340 KB Ok
26 Correct 0 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 1 ms 340 KB Ok
29 Correct 0 ms 340 KB Ok
30 Correct 0 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 5 ms 596 KB Ok
35 Correct 5 ms 588 KB Ok
36 Correct 5 ms 596 KB Ok
37 Correct 5 ms 596 KB Ok
38 Correct 4 ms 608 KB Ok
39 Correct 4 ms 724 KB Ok
40 Correct 4 ms 592 KB Ok
41 Correct 5 ms 596 KB Ok
42 Correct 5 ms 596 KB Ok
43 Correct 5 ms 580 KB Ok
44 Correct 11 ms 900 KB Ok
45 Correct 11 ms 972 KB Ok
46 Correct 11 ms 984 KB Ok
47 Correct 10 ms 964 KB Ok
48 Correct 10 ms 980 KB Ok
49 Correct 10 ms 980 KB Ok
50 Correct 11 ms 980 KB Ok
51 Correct 11 ms 980 KB Ok
52 Correct 11 ms 916 KB Ok
53 Correct 11 ms 1036 KB Ok
54 Correct 203 ms 9164 KB Ok
55 Correct 239 ms 9548 KB Ok
56 Correct 240 ms 9408 KB Ok
57 Correct 165 ms 8652 KB Ok
58 Correct 222 ms 9420 KB Ok
59 Correct 230 ms 9364 KB Ok
60 Correct 176 ms 8928 KB Ok
61 Correct 170 ms 8868 KB Ok
62 Correct 262 ms 9684 KB Ok
63 Correct 205 ms 9148 KB Ok
64 Correct 251 ms 9492 KB Ok
65 Correct 226 ms 9328 KB Ok
66 Correct 187 ms 8972 KB Ok
67 Correct 164 ms 8640 KB Ok
68 Correct 222 ms 9284 KB Ok
69 Correct 779 ms 19472 KB Ok
70 Correct 749 ms 19920 KB Ok
71 Correct 721 ms 19588 KB Ok
72 Correct 690 ms 19500 KB Ok
73 Correct 739 ms 19752 KB Ok
74 Correct 698 ms 19448 KB Ok
75 Correct 694 ms 19628 KB Ok
76 Correct 829 ms 19560 KB Ok
77 Correct 662 ms 19448 KB Ok
78 Correct 752 ms 19456 KB Ok
79 Correct 735 ms 19944 KB Ok
80 Correct 703 ms 19456 KB Ok
81 Correct 713 ms 19972 KB Ok
82 Correct 723 ms 19476 KB Ok
83 Correct 708 ms 19552 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 284 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 340 KB Ok
9 Correct 1 ms 328 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 1 ms 328 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 1 ms 328 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 328 KB Ok
18 Correct 6 ms 880 KB Ok
19 Correct 27 ms 3004 KB Ok
20 Correct 13 ms 1580 KB Ok
21 Correct 35 ms 3516 KB Ok
22 Correct 19 ms 2124 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 1 ms 292 KB Ok
25 Correct 1 ms 340 KB Ok
26 Correct 0 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 1 ms 340 KB Ok
29 Correct 0 ms 340 KB Ok
30 Correct 0 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 1 ms 324 KB Ok
35 Correct 1 ms 344 KB Ok
36 Correct 1 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 1 ms 340 KB Ok
39 Correct 358 ms 24568 KB Ok
40 Correct 292 ms 28108 KB Ok
41 Correct 642 ms 30048 KB Ok
42 Correct 460 ms 27868 KB Ok
43 Correct 243 ms 16916 KB Ok
44 Correct 505 ms 30772 KB Ok
45 Correct 5 ms 596 KB Ok
46 Correct 5 ms 588 KB Ok
47 Correct 5 ms 596 KB Ok
48 Correct 5 ms 596 KB Ok
49 Correct 4 ms 608 KB Ok
50 Correct 4 ms 724 KB Ok
51 Correct 4 ms 592 KB Ok
52 Correct 5 ms 596 KB Ok
53 Correct 5 ms 596 KB Ok
54 Correct 5 ms 580 KB Ok
55 Correct 11 ms 900 KB Ok
56 Correct 11 ms 972 KB Ok
57 Correct 11 ms 984 KB Ok
58 Correct 10 ms 964 KB Ok
59 Correct 10 ms 980 KB Ok
60 Correct 10 ms 980 KB Ok
61 Correct 11 ms 980 KB Ok
62 Correct 11 ms 980 KB Ok
63 Correct 11 ms 916 KB Ok
64 Correct 11 ms 1036 KB Ok
65 Correct 203 ms 9164 KB Ok
66 Correct 239 ms 9548 KB Ok
67 Correct 240 ms 9408 KB Ok
68 Correct 165 ms 8652 KB Ok
69 Correct 222 ms 9420 KB Ok
70 Correct 230 ms 9364 KB Ok
71 Correct 176 ms 8928 KB Ok
72 Correct 170 ms 8868 KB Ok
73 Correct 262 ms 9684 KB Ok
74 Correct 205 ms 9148 KB Ok
75 Correct 251 ms 9492 KB Ok
76 Correct 226 ms 9328 KB Ok
77 Correct 187 ms 8972 KB Ok
78 Correct 164 ms 8640 KB Ok
79 Correct 222 ms 9284 KB Ok
80 Correct 779 ms 19472 KB Ok
81 Correct 749 ms 19920 KB Ok
82 Correct 721 ms 19588 KB Ok
83 Correct 690 ms 19500 KB Ok
84 Correct 739 ms 19752 KB Ok
85 Correct 698 ms 19448 KB Ok
86 Correct 694 ms 19628 KB Ok
87 Correct 829 ms 19560 KB Ok
88 Correct 662 ms 19448 KB Ok
89 Correct 752 ms 19456 KB Ok
90 Correct 735 ms 19944 KB Ok
91 Correct 703 ms 19456 KB Ok
92 Correct 713 ms 19972 KB Ok
93 Correct 723 ms 19476 KB Ok
94 Correct 708 ms 19552 KB Ok
95 Correct 620 ms 31432 KB Ok
96 Correct 933 ms 35316 KB Ok
97 Correct 899 ms 34136 KB Ok
98 Correct 615 ms 32076 KB Ok
99 Correct 707 ms 31876 KB Ok
100 Correct 867 ms 34108 KB Ok
101 Correct 762 ms 33672 KB Ok
102 Correct 787 ms 33152 KB Ok
103 Correct 922 ms 34056 KB Ok
104 Correct 981 ms 35272 KB Ok
105 Correct 978 ms 34828 KB Ok
106 Correct 752 ms 32656 KB Ok
107 Correct 828 ms 34244 KB Ok
108 Correct 1160 ms 35276 KB Ok
109 Correct 954 ms 34840 KB Ok
110 Execution timed out 2081 ms 47828 KB Time limit exceeded
111 Halted 0 ms 0 KB -