oj.uz

Submission #689409

# Submission time Handle Problem Language Result Execution time Memory
689409 2023-01-28T12:28:32 Z gesgha Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 56984 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 = 4e5 + 10;
const bool TEST = 1;

void precalc() {}

int G[N][3];
int sz[N];
int a[N];
int sz_A;
bool vis[N];
int ptr[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;
}


bool visn[N];

bool is_cycle(int v) {
    a[sz_A++] = v;
    visn[v] = 1;
    vis[v] = 1;
    bool ok = 0;
    fr(i, 0, sz[v] - 1) {
        if (visn[G[v][i]]) return 1;
        if (!vis[G[v][i]]) {
            ok |= is_cycle(G[v][i]);
            if (ok) return 1;
        }
    }
    return 0;
}


bool can(int n, int m, int k) {
    sz_A = 0;
    fr(i, 0, k) sz[i] = ptr[i] = 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);
    }
    bool ok = 0;
    fr(i, 0, k) {
        if (vis[i]) continue;
        ok |= is_cycle(i);
        fr(i, 0, sz_A - 1) visn[a[i]] = 0;
        sz_A = 0;
        if (ok) 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 = 2 * 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;
        ptr[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 0 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 340 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 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 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 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 352 KB Ok
6 Correct 4 ms 596 KB Ok
7 Correct 20 ms 1620 KB Ok
8 Correct 9 ms 936 KB Ok
9 Correct 24 ms 1812 KB Ok
10 Correct 12 ms 1108 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 321 ms 18804 KB Ok
7 Correct 223 ms 21396 KB Ok
8 Correct 491 ms 23164 KB Ok
9 Correct 327 ms 22116 KB Ok
10 Correct 215 ms 12756 KB Ok
11 Correct 389 ms 24000 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 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 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 0 ms 340 KB Ok
19 Correct 0 ms 340 KB Ok
20 Correct 1 ms 340 KB Ok
21 Correct 0 ms 340 KB Ok
22 Correct 0 ms 340 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 3 ms 468 KB Ok
25 Correct 4 ms 468 KB Ok
26 Correct 3 ms 468 KB Ok
27 Correct 3 ms 468 KB Ok
28 Correct 2 ms 468 KB Ok
29 Correct 2 ms 468 KB Ok
30 Correct 2 ms 468 KB Ok
31 Correct 3 ms 468 KB Ok
32 Correct 4 ms 468 KB Ok
33 Correct 3 ms 468 KB Ok
34 Correct 8 ms 852 KB Ok
35 Correct 8 ms 852 KB Ok
36 Correct 9 ms 844 KB Ok
37 Correct 11 ms 872 KB Ok
38 Correct 9 ms 888 KB Ok
39 Correct 8 ms 852 KB Ok
40 Correct 9 ms 852 KB Ok
41 Correct 9 ms 852 KB Ok
42 Correct 8 ms 872 KB Ok
43 Correct 9 ms 856 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 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 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 352 KB Ok
18 Correct 4 ms 596 KB Ok
19 Correct 20 ms 1620 KB Ok
20 Correct 9 ms 936 KB Ok
21 Correct 24 ms 1812 KB Ok
22 Correct 12 ms 1108 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 0 ms 340 KB Ok
29 Correct 0 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 0 ms 340 KB Ok
34 Correct 3 ms 468 KB Ok
35 Correct 4 ms 468 KB Ok
36 Correct 3 ms 468 KB Ok
37 Correct 3 ms 468 KB Ok
38 Correct 2 ms 468 KB Ok
39 Correct 2 ms 468 KB Ok
40 Correct 2 ms 468 KB Ok
41 Correct 3 ms 468 KB Ok
42 Correct 4 ms 468 KB Ok
43 Correct 3 ms 468 KB Ok
44 Correct 8 ms 852 KB Ok
45 Correct 8 ms 852 KB Ok
46 Correct 9 ms 844 KB Ok
47 Correct 11 ms 872 KB Ok
48 Correct 9 ms 888 KB Ok
49 Correct 8 ms 852 KB Ok
50 Correct 9 ms 852 KB Ok
51 Correct 9 ms 852 KB Ok
52 Correct 8 ms 872 KB Ok
53 Correct 9 ms 856 KB Ok
54 Correct 134 ms 5560 KB Ok
55 Correct 180 ms 5976 KB Ok
56 Correct 153 ms 5964 KB Ok
57 Correct 111 ms 4956 KB Ok
58 Correct 140 ms 5808 KB Ok
59 Correct 139 ms 5624 KB Ok
60 Correct 113 ms 5028 KB Ok
61 Correct 112 ms 5324 KB Ok
62 Correct 179 ms 6164 KB Ok
63 Correct 128 ms 5344 KB Ok
64 Correct 169 ms 5952 KB Ok
65 Correct 146 ms 5856 KB Ok
66 Correct 132 ms 5404 KB Ok
67 Correct 112 ms 5180 KB Ok
68 Correct 153 ms 5656 KB Ok
69 Correct 445 ms 16064 KB Ok
70 Correct 453 ms 16432 KB Ok
71 Correct 401 ms 16020 KB Ok
72 Correct 427 ms 15848 KB Ok
73 Correct 451 ms 16332 KB Ok
74 Correct 381 ms 15916 KB Ok
75 Correct 394 ms 15996 KB Ok
76 Correct 458 ms 16156 KB Ok
77 Correct 368 ms 15908 KB Ok
78 Correct 476 ms 15860 KB Ok
79 Correct 403 ms 16384 KB Ok
80 Correct 413 ms 15932 KB Ok
81 Correct 406 ms 16332 KB Ok
82 Correct 444 ms 16024 KB Ok
83 Correct 416 ms 16220 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 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 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 1 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 1 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 352 KB Ok
18 Correct 4 ms 596 KB Ok
19 Correct 20 ms 1620 KB Ok
20 Correct 9 ms 936 KB Ok
21 Correct 24 ms 1812 KB Ok
22 Correct 12 ms 1108 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 1 ms 340 KB Ok
28 Correct 0 ms 340 KB Ok
29 Correct 0 ms 340 KB Ok
30 Correct 1 ms 340 KB Ok
31 Correct 0 ms 340 KB Ok
32 Correct 0 ms 340 KB Ok
33 Correct 0 ms 340 KB Ok
34 Correct 0 ms 340 KB Ok
35 Correct 0 ms 340 KB Ok
36 Correct 0 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 1 ms 340 KB Ok
39 Correct 321 ms 18804 KB Ok
40 Correct 223 ms 21396 KB Ok
41 Correct 491 ms 23164 KB Ok
42 Correct 327 ms 22116 KB Ok
43 Correct 215 ms 12756 KB Ok
44 Correct 389 ms 24000 KB Ok
45 Correct 3 ms 468 KB Ok
46 Correct 4 ms 468 KB Ok
47 Correct 3 ms 468 KB Ok
48 Correct 3 ms 468 KB Ok
49 Correct 2 ms 468 KB Ok
50 Correct 2 ms 468 KB Ok
51 Correct 2 ms 468 KB Ok
52 Correct 3 ms 468 KB Ok
53 Correct 4 ms 468 KB Ok
54 Correct 3 ms 468 KB Ok
55 Correct 8 ms 852 KB Ok
56 Correct 8 ms 852 KB Ok
57 Correct 9 ms 844 KB Ok
58 Correct 11 ms 872 KB Ok
59 Correct 9 ms 888 KB Ok
60 Correct 8 ms 852 KB Ok
61 Correct 9 ms 852 KB Ok
62 Correct 9 ms 852 KB Ok
63 Correct 8 ms 872 KB Ok
64 Correct 9 ms 856 KB Ok
65 Correct 134 ms 5560 KB Ok
66 Correct 180 ms 5976 KB Ok
67 Correct 153 ms 5964 KB Ok
68 Correct 111 ms 4956 KB Ok
69 Correct 140 ms 5808 KB Ok
70 Correct 139 ms 5624 KB Ok
71 Correct 113 ms 5028 KB Ok
72 Correct 112 ms 5324 KB Ok
73 Correct 179 ms 6164 KB Ok
74 Correct 128 ms 5344 KB Ok
75 Correct 169 ms 5952 KB Ok
76 Correct 146 ms 5856 KB Ok
77 Correct 132 ms 5404 KB Ok
78 Correct 112 ms 5180 KB Ok
79 Correct 153 ms 5656 KB Ok
80 Correct 445 ms 16064 KB Ok
81 Correct 453 ms 16432 KB Ok
82 Correct 401 ms 16020 KB Ok
83 Correct 427 ms 15848 KB Ok
84 Correct 451 ms 16332 KB Ok
85 Correct 381 ms 15916 KB Ok
86 Correct 394 ms 15996 KB Ok
87 Correct 458 ms 16156 KB Ok
88 Correct 368 ms 15908 KB Ok
89 Correct 476 ms 15860 KB Ok
90 Correct 403 ms 16384 KB Ok
91 Correct 413 ms 15932 KB Ok
92 Correct 406 ms 16332 KB Ok
93 Correct 444 ms 16024 KB Ok
94 Correct 416 ms 16220 KB Ok
95 Correct 314 ms 15176 KB Ok
96 Correct 576 ms 20816 KB Ok
97 Correct 548 ms 17696 KB Ok
98 Correct 341 ms 17184 KB Ok
99 Correct 440 ms 16552 KB Ok
100 Correct 486 ms 17632 KB Ok
101 Correct 536 ms 18408 KB Ok
102 Correct 449 ms 17580 KB Ok
103 Correct 462 ms 18964 KB Ok
104 Correct 530 ms 20128 KB Ok
105 Correct 541 ms 20544 KB Ok
106 Correct 374 ms 19148 KB Ok
107 Correct 548 ms 19212 KB Ok
108 Correct 567 ms 20808 KB Ok
109 Correct 446 ms 20612 KB Ok
110 Execution timed out 2097 ms 56984 KB Time limit exceeded
111 Halted 0 ms 0 KB -