oj.uz

Submission #689407

# Submission time Handle Problem Language Result Execution time Memory
689407 2023-01-28T12:24:19 Z gesgha Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 62216 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][10];
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 372 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 0 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 1 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 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 4 ms 596 KB Ok
7 Correct 20 ms 2004 KB Ok
8 Correct 9 ms 1028 KB Ok
9 Correct 24 ms 2264 KB Ok
10 Correct 13 ms 1364 KB Ok

Subtask #3
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 0 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 1 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 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 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 0 ms 340 KB Ok
6 Correct 316 ms 23304 KB Ok
7 Correct 255 ms 26700 KB Ok
8 Correct 583 ms 28532 KB Ok
9 Correct 394 ms 26700 KB Ok
10 Correct 222 ms 16052 KB Ok
11 Correct 460 ms 29408 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 372 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 0 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 1 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 0 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 1 ms 340 KB Ok
22 Correct 1 ms 340 KB Ok
23 Correct 1 ms 340 KB Ok
24 Correct 3 ms 596 KB Ok
25 Correct 3 ms 596 KB Ok
26 Correct 4 ms 596 KB Ok
27 Correct 3 ms 596 KB Ok
28 Correct 4 ms 468 KB Ok
29 Correct 3 ms 596 KB Ok
30 Correct 3 ms 468 KB Ok
31 Correct 4 ms 596 KB Ok
32 Correct 3 ms 468 KB Ok
33 Correct 3 ms 596 KB Ok
34 Correct 9 ms 980 KB Ok
35 Correct 9 ms 920 KB Ok
36 Correct 11 ms 984 KB Ok
37 Correct 9 ms 936 KB Ok
38 Correct 8 ms 980 KB Ok
39 Correct 8 ms 852 KB Ok
40 Correct 12 ms 1088 KB Ok
41 Correct 9 ms 980 KB Ok
42 Correct 9 ms 980 KB Ok
43 Correct 9 ms 980 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 372 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 0 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 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 4 ms 596 KB Ok
19 Correct 20 ms 2004 KB Ok
20 Correct 9 ms 1028 KB Ok
21 Correct 24 ms 2264 KB Ok
22 Correct 13 ms 1364 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 0 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 1 ms 340 KB Ok
32 Correct 1 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 3 ms 596 KB Ok
35 Correct 3 ms 596 KB Ok
36 Correct 4 ms 596 KB Ok
37 Correct 3 ms 596 KB Ok
38 Correct 4 ms 468 KB Ok
39 Correct 3 ms 596 KB Ok
40 Correct 3 ms 468 KB Ok
41 Correct 4 ms 596 KB Ok
42 Correct 3 ms 468 KB Ok
43 Correct 3 ms 596 KB Ok
44 Correct 9 ms 980 KB Ok
45 Correct 9 ms 920 KB Ok
46 Correct 11 ms 984 KB Ok
47 Correct 9 ms 936 KB Ok
48 Correct 8 ms 980 KB Ok
49 Correct 8 ms 852 KB Ok
50 Correct 12 ms 1088 KB Ok
51 Correct 9 ms 980 KB Ok
52 Correct 9 ms 980 KB Ok
53 Correct 9 ms 980 KB Ok
54 Correct 135 ms 8068 KB Ok
55 Correct 176 ms 8476 KB Ok
56 Correct 158 ms 8428 KB Ok
57 Correct 135 ms 7372 KB Ok
58 Correct 146 ms 8328 KB Ok
59 Correct 144 ms 7836 KB Ok
60 Correct 118 ms 7472 KB Ok
61 Correct 117 ms 7876 KB Ok
62 Correct 202 ms 8776 KB Ok
63 Correct 142 ms 7764 KB Ok
64 Correct 175 ms 8416 KB Ok
65 Correct 155 ms 8332 KB Ok
66 Correct 141 ms 7948 KB Ok
67 Correct 126 ms 7528 KB Ok
68 Correct 158 ms 8364 KB Ok
69 Correct 526 ms 18760 KB Ok
70 Correct 627 ms 19092 KB Ok
71 Correct 504 ms 18800 KB Ok
72 Correct 496 ms 18664 KB Ok
73 Correct 578 ms 18980 KB Ok
74 Correct 497 ms 18640 KB Ok
75 Correct 459 ms 18696 KB Ok
76 Correct 617 ms 18852 KB Ok
77 Correct 481 ms 18636 KB Ok
78 Correct 657 ms 18644 KB Ok
79 Correct 545 ms 19020 KB Ok
80 Correct 525 ms 18756 KB Ok
81 Correct 570 ms 19096 KB Ok
82 Correct 627 ms 18856 KB Ok
83 Correct 510 ms 18844 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 1 ms 372 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 0 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 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 4 ms 596 KB Ok
19 Correct 20 ms 2004 KB Ok
20 Correct 9 ms 1028 KB Ok
21 Correct 24 ms 2264 KB Ok
22 Correct 13 ms 1364 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 0 ms 340 KB Ok
25 Correct 0 ms 340 KB Ok
26 Correct 1 ms 340 KB Ok
27 Correct 0 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 1 ms 340 KB Ok
32 Correct 1 ms 340 KB Ok
33 Correct 1 ms 340 KB Ok
34 Correct 0 ms 340 KB Ok
35 Correct 1 ms 340 KB Ok
36 Correct 1 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 0 ms 340 KB Ok
39 Correct 316 ms 23304 KB Ok
40 Correct 255 ms 26700 KB Ok
41 Correct 583 ms 28532 KB Ok
42 Correct 394 ms 26700 KB Ok
43 Correct 222 ms 16052 KB Ok
44 Correct 460 ms 29408 KB Ok
45 Correct 3 ms 596 KB Ok
46 Correct 3 ms 596 KB Ok
47 Correct 4 ms 596 KB Ok
48 Correct 3 ms 596 KB Ok
49 Correct 4 ms 468 KB Ok
50 Correct 3 ms 596 KB Ok
51 Correct 3 ms 468 KB Ok
52 Correct 4 ms 596 KB Ok
53 Correct 3 ms 468 KB Ok
54 Correct 3 ms 596 KB Ok
55 Correct 9 ms 980 KB Ok
56 Correct 9 ms 920 KB Ok
57 Correct 11 ms 984 KB Ok
58 Correct 9 ms 936 KB Ok
59 Correct 8 ms 980 KB Ok
60 Correct 8 ms 852 KB Ok
61 Correct 12 ms 1088 KB Ok
62 Correct 9 ms 980 KB Ok
63 Correct 9 ms 980 KB Ok
64 Correct 9 ms 980 KB Ok
65 Correct 135 ms 8068 KB Ok
66 Correct 176 ms 8476 KB Ok
67 Correct 158 ms 8428 KB Ok
68 Correct 135 ms 7372 KB Ok
69 Correct 146 ms 8328 KB Ok
70 Correct 144 ms 7836 KB Ok
71 Correct 118 ms 7472 KB Ok
72 Correct 117 ms 7876 KB Ok
73 Correct 202 ms 8776 KB Ok
74 Correct 142 ms 7764 KB Ok
75 Correct 175 ms 8416 KB Ok
76 Correct 155 ms 8332 KB Ok
77 Correct 141 ms 7948 KB Ok
78 Correct 126 ms 7528 KB Ok
79 Correct 158 ms 8364 KB Ok
80 Correct 526 ms 18760 KB Ok
81 Correct 627 ms 19092 KB Ok
82 Correct 504 ms 18800 KB Ok
83 Correct 496 ms 18664 KB Ok
84 Correct 578 ms 18980 KB Ok
85 Correct 497 ms 18640 KB Ok
86 Correct 459 ms 18696 KB Ok
87 Correct 617 ms 18852 KB Ok
88 Correct 481 ms 18636 KB Ok
89 Correct 657 ms 18644 KB Ok
90 Correct 545 ms 19020 KB Ok
91 Correct 525 ms 18756 KB Ok
92 Correct 570 ms 19096 KB Ok
93 Correct 627 ms 18856 KB Ok
94 Correct 510 ms 18844 KB Ok
95 Correct 396 ms 23228 KB Ok
96 Correct 745 ms 31000 KB Ok
97 Correct 625 ms 25860 KB Ok
98 Correct 386 ms 26536 KB Ok
99 Correct 525 ms 24332 KB Ok
100 Correct 735 ms 25804 KB Ok
101 Correct 666 ms 27708 KB Ok
102 Correct 598 ms 25772 KB Ok
103 Correct 648 ms 28412 KB Ok
104 Correct 727 ms 29680 KB Ok
105 Correct 671 ms 30540 KB Ok
106 Correct 494 ms 29248 KB Ok
107 Correct 626 ms 28628 KB Ok
108 Correct 731 ms 30680 KB Ok
109 Correct 593 ms 31200 KB Ok
110 Execution timed out 2072 ms 62216 KB Time limit exceeded
111 Halted 0 ms 0 KB -