oj.uz

Submission #689410

# Submission time Handle Problem Language Result Execution time Memory
689410 2023-01-28T12:30:15 Z gesgha Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 58572 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][4];
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 = 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 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok

Subtask #2
9.0 / 9.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 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 2 ms 596 KB Ok
7 Correct 12 ms 1524 KB Ok
8 Correct 5 ms 844 KB Ok
9 Correct 15 ms 1748 KB Ok
10 Correct 7 ms 1096 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 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 1 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 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 340 KB Ok
6 Correct 286 ms 19464 KB Ok
7 Correct 231 ms 22092 KB Ok
8 Correct 450 ms 23980 KB Ok
9 Correct 335 ms 22760 KB Ok
10 Correct 221 ms 13260 KB Ok
11 Correct 369 ms 24756 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Correct 1 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 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 1 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 3 ms 468 KB Ok
26 Correct 4 ms 468 KB Ok
27 Correct 3 ms 468 KB Ok
28 Correct 3 ms 468 KB Ok
29 Correct 2 ms 468 KB Ok
30 Correct 2 ms 468 KB Ok
31 Correct 4 ms 468 KB Ok
32 Correct 4 ms 468 KB Ok
33 Correct 3 ms 468 KB Ok
34 Correct 8 ms 804 KB Ok
35 Correct 7 ms 852 KB Ok
36 Correct 8 ms 852 KB Ok
37 Correct 8 ms 852 KB Ok
38 Correct 8 ms 852 KB Ok
39 Correct 7 ms 852 KB Ok
40 Correct 9 ms 852 KB Ok
41 Correct 9 ms 852 KB Ok
42 Correct 9 ms 840 KB Ok
43 Correct 8 ms 848 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 0 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 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 2 ms 596 KB Ok
19 Correct 12 ms 1524 KB Ok
20 Correct 5 ms 844 KB Ok
21 Correct 15 ms 1748 KB Ok
22 Correct 7 ms 1096 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 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 1 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 3 ms 468 KB Ok
36 Correct 4 ms 468 KB Ok
37 Correct 3 ms 468 KB Ok
38 Correct 3 ms 468 KB Ok
39 Correct 2 ms 468 KB Ok
40 Correct 2 ms 468 KB Ok
41 Correct 4 ms 468 KB Ok
42 Correct 4 ms 468 KB Ok
43 Correct 3 ms 468 KB Ok
44 Correct 8 ms 804 KB Ok
45 Correct 7 ms 852 KB Ok
46 Correct 8 ms 852 KB Ok
47 Correct 8 ms 852 KB Ok
48 Correct 8 ms 852 KB Ok
49 Correct 7 ms 852 KB Ok
50 Correct 9 ms 852 KB Ok
51 Correct 9 ms 852 KB Ok
52 Correct 9 ms 840 KB Ok
53 Correct 8 ms 848 KB Ok
54 Correct 135 ms 5932 KB Ok
55 Correct 173 ms 6240 KB Ok
56 Correct 159 ms 6292 KB Ok
57 Correct 117 ms 5376 KB Ok
58 Correct 153 ms 6196 KB Ok
59 Correct 139 ms 5884 KB Ok
60 Correct 113 ms 5240 KB Ok
61 Correct 122 ms 5660 KB Ok
62 Correct 181 ms 6576 KB Ok
63 Correct 134 ms 5708 KB Ok
64 Correct 168 ms 6220 KB Ok
65 Correct 169 ms 6184 KB Ok
66 Correct 131 ms 5816 KB Ok
67 Correct 109 ms 5448 KB Ok
68 Correct 153 ms 6084 KB Ok
69 Correct 427 ms 16472 KB Ok
70 Correct 421 ms 16748 KB Ok
71 Correct 417 ms 16412 KB Ok
72 Correct 404 ms 16404 KB Ok
73 Correct 411 ms 16608 KB Ok
74 Correct 391 ms 16292 KB Ok
75 Correct 388 ms 16296 KB Ok
76 Correct 416 ms 16484 KB Ok
77 Correct 383 ms 16292 KB Ok
78 Correct 446 ms 16292 KB Ok
79 Correct 393 ms 16688 KB Ok
80 Correct 411 ms 16332 KB Ok
81 Correct 419 ms 16756 KB Ok
82 Correct 411 ms 16400 KB Ok
83 Correct 404 ms 16448 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 1 ms 340 KB Ok
12 Correct 0 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 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 2 ms 596 KB Ok
19 Correct 12 ms 1524 KB Ok
20 Correct 5 ms 844 KB Ok
21 Correct 15 ms 1748 KB Ok
22 Correct 7 ms 1096 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 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 1 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 1 ms 340 KB Ok
35 Correct 1 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 286 ms 19464 KB Ok
40 Correct 231 ms 22092 KB Ok
41 Correct 450 ms 23980 KB Ok
42 Correct 335 ms 22760 KB Ok
43 Correct 221 ms 13260 KB Ok
44 Correct 369 ms 24756 KB Ok
45 Correct 3 ms 468 KB Ok
46 Correct 3 ms 468 KB Ok
47 Correct 4 ms 468 KB Ok
48 Correct 3 ms 468 KB Ok
49 Correct 3 ms 468 KB Ok
50 Correct 2 ms 468 KB Ok
51 Correct 2 ms 468 KB Ok
52 Correct 4 ms 468 KB Ok
53 Correct 4 ms 468 KB Ok
54 Correct 3 ms 468 KB Ok
55 Correct 8 ms 804 KB Ok
56 Correct 7 ms 852 KB Ok
57 Correct 8 ms 852 KB Ok
58 Correct 8 ms 852 KB Ok
59 Correct 8 ms 852 KB Ok
60 Correct 7 ms 852 KB Ok
61 Correct 9 ms 852 KB Ok
62 Correct 9 ms 852 KB Ok
63 Correct 9 ms 840 KB Ok
64 Correct 8 ms 848 KB Ok
65 Correct 135 ms 5932 KB Ok
66 Correct 173 ms 6240 KB Ok
67 Correct 159 ms 6292 KB Ok
68 Correct 117 ms 5376 KB Ok
69 Correct 153 ms 6196 KB Ok
70 Correct 139 ms 5884 KB Ok
71 Correct 113 ms 5240 KB Ok
72 Correct 122 ms 5660 KB Ok
73 Correct 181 ms 6576 KB Ok
74 Correct 134 ms 5708 KB Ok
75 Correct 168 ms 6220 KB Ok
76 Correct 169 ms 6184 KB Ok
77 Correct 131 ms 5816 KB Ok
78 Correct 109 ms 5448 KB Ok
79 Correct 153 ms 6084 KB Ok
80 Correct 427 ms 16472 KB Ok
81 Correct 421 ms 16748 KB Ok
82 Correct 417 ms 16412 KB Ok
83 Correct 404 ms 16404 KB Ok
84 Correct 411 ms 16608 KB Ok
85 Correct 391 ms 16292 KB Ok
86 Correct 388 ms 16296 KB Ok
87 Correct 416 ms 16484 KB Ok
88 Correct 383 ms 16292 KB Ok
89 Correct 446 ms 16292 KB Ok
90 Correct 393 ms 16688 KB Ok
91 Correct 411 ms 16332 KB Ok
92 Correct 419 ms 16756 KB Ok
93 Correct 411 ms 16400 KB Ok
94 Correct 404 ms 16448 KB Ok
95 Correct 311 ms 15128 KB Ok
96 Correct 519 ms 22088 KB Ok
97 Correct 561 ms 18660 KB Ok
98 Correct 367 ms 18024 KB Ok
99 Correct 419 ms 17920 KB Ok
100 Correct 519 ms 17948 KB Ok
101 Correct 495 ms 19788 KB Ok
102 Correct 457 ms 18528 KB Ok
103 Correct 505 ms 19584 KB Ok
104 Correct 565 ms 21288 KB Ok
105 Correct 581 ms 21588 KB Ok
106 Correct 396 ms 20504 KB Ok
107 Correct 509 ms 20520 KB Ok
108 Correct 629 ms 21796 KB Ok
109 Correct 521 ms 21864 KB Ok
110 Execution timed out 2097 ms 58572 KB Time limit exceeded
111 Halted 0 ms 0 KB -