oj.uz

Submission #689399

# Submission time Handle Problem Language Result Execution time Memory
689399 2023-01-28T11:59:57 Z gesgha Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 30944 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];
int ptr[N];

void dfs(int v) {

    stack <int> st;
    st.push(v);
    while (sz(st)) {
        int v = st.top();
        vis[v] = 1;
        while(ptr[v] < sz[v] && vis[G[v][ptr[v]]]) ptr[v]++;
        if (ptr[v] == sz[v]) {
            a[sz_A++] = v;
            st.pop();
            continue;
        } else {
            st.push(G[v][sz[v] - 1]);
            ptr[v]++;
            continue;
        }
    }
    return;
    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;
    }
    return res;
}

bool can(int n, int m, int k) {
    fr(i, 0, k) {
        sz[i] = 0;
        ptr[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 = 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 1 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 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 1 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 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 340 KB Ok
6 Correct 7 ms 596 KB Ok
7 Correct 36 ms 1484 KB Ok
8 Correct 16 ms 852 KB Ok
9 Correct 41 ms 1676 KB Ok
10 Correct 23 ms 1072 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 1 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 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 1 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 1 ms 340 KB Ok
6 Correct 426 ms 14196 KB Ok
7 Correct 424 ms 14752 KB Ok
8 Correct 817 ms 17560 KB Ok
9 Correct 595 ms 16844 KB Ok
10 Correct 296 ms 10480 KB Ok
11 Correct 495 ms 17488 KB Ok

Subtask #5
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 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 1 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 1 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 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 9 ms 596 KB Ok
25 Correct 8 ms 596 KB Ok
26 Correct 9 ms 604 KB Ok
27 Correct 8 ms 596 KB Ok
28 Correct 8 ms 468 KB Ok
29 Correct 8 ms 596 KB Ok
30 Correct 6 ms 468 KB Ok
31 Correct 8 ms 596 KB Ok
32 Correct 8 ms 468 KB Ok
33 Correct 10 ms 596 KB Ok
34 Correct 13 ms 724 KB Ok
35 Correct 13 ms 724 KB Ok
36 Correct 14 ms 724 KB Ok
37 Correct 13 ms 728 KB Ok
38 Correct 15 ms 756 KB Ok
39 Correct 13 ms 724 KB Ok
40 Correct 14 ms 772 KB Ok
41 Correct 13 ms 676 KB Ok
42 Correct 14 ms 732 KB Ok
43 Correct 17 ms 724 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 1 ms 340 KB Ok
11 Correct 1 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 1 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 7 ms 596 KB Ok
19 Correct 36 ms 1484 KB Ok
20 Correct 16 ms 852 KB Ok
21 Correct 41 ms 1676 KB Ok
22 Correct 23 ms 1072 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 1 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 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 9 ms 596 KB Ok
35 Correct 8 ms 596 KB Ok
36 Correct 9 ms 604 KB Ok
37 Correct 8 ms 596 KB Ok
38 Correct 8 ms 468 KB Ok
39 Correct 8 ms 596 KB Ok
40 Correct 6 ms 468 KB Ok
41 Correct 8 ms 596 KB Ok
42 Correct 8 ms 468 KB Ok
43 Correct 10 ms 596 KB Ok
44 Correct 13 ms 724 KB Ok
45 Correct 13 ms 724 KB Ok
46 Correct 14 ms 724 KB Ok
47 Correct 13 ms 728 KB Ok
48 Correct 15 ms 756 KB Ok
49 Correct 13 ms 724 KB Ok
50 Correct 14 ms 772 KB Ok
51 Correct 13 ms 676 KB Ok
52 Correct 14 ms 732 KB Ok
53 Correct 17 ms 724 KB Ok
54 Correct 431 ms 7992 KB Ok
55 Correct 520 ms 8460 KB Ok
56 Correct 624 ms 8448 KB Ok
57 Correct 396 ms 7308 KB Ok
58 Correct 455 ms 8284 KB Ok
59 Correct 449 ms 7796 KB Ok
60 Correct 469 ms 7424 KB Ok
61 Correct 463 ms 7764 KB Ok
62 Correct 528 ms 8700 KB Ok
63 Correct 446 ms 7660 KB Ok
64 Correct 491 ms 8384 KB Ok
65 Correct 507 ms 8172 KB Ok
66 Correct 476 ms 7920 KB Ok
67 Correct 441 ms 7464 KB Ok
68 Correct 424 ms 8224 KB Ok
69 Correct 1053 ms 12552 KB Ok
70 Correct 819 ms 13200 KB Ok
71 Correct 754 ms 12632 KB Ok
72 Correct 760 ms 12588 KB Ok
73 Correct 795 ms 12792 KB Ok
74 Correct 716 ms 12456 KB Ok
75 Correct 790 ms 12568 KB Ok
76 Correct 823 ms 12688 KB Ok
77 Correct 761 ms 12460 KB Ok
78 Correct 767 ms 12600 KB Ok
79 Correct 799 ms 13028 KB Ok
80 Correct 741 ms 12564 KB Ok
81 Correct 746 ms 12800 KB Ok
82 Correct 750 ms 12600 KB Ok
83 Correct 760 ms 12860 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 1 ms 340 KB Ok
11 Correct 1 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 1 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 7 ms 596 KB Ok
19 Correct 36 ms 1484 KB Ok
20 Correct 16 ms 852 KB Ok
21 Correct 41 ms 1676 KB Ok
22 Correct 23 ms 1072 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 1 ms 340 KB Ok
25 Correct 1 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 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 1 ms 340 KB Ok
35 Correct 0 ms 340 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 426 ms 14196 KB Ok
40 Correct 424 ms 14752 KB Ok
41 Correct 817 ms 17560 KB Ok
42 Correct 595 ms 16844 KB Ok
43 Correct 296 ms 10480 KB Ok
44 Correct 495 ms 17488 KB Ok
45 Correct 9 ms 596 KB Ok
46 Correct 8 ms 596 KB Ok
47 Correct 9 ms 604 KB Ok
48 Correct 8 ms 596 KB Ok
49 Correct 8 ms 468 KB Ok
50 Correct 8 ms 596 KB Ok
51 Correct 6 ms 468 KB Ok
52 Correct 8 ms 596 KB Ok
53 Correct 8 ms 468 KB Ok
54 Correct 10 ms 596 KB Ok
55 Correct 13 ms 724 KB Ok
56 Correct 13 ms 724 KB Ok
57 Correct 14 ms 724 KB Ok
58 Correct 13 ms 728 KB Ok
59 Correct 15 ms 756 KB Ok
60 Correct 13 ms 724 KB Ok
61 Correct 14 ms 772 KB Ok
62 Correct 13 ms 676 KB Ok
63 Correct 14 ms 732 KB Ok
64 Correct 17 ms 724 KB Ok
65 Correct 431 ms 7992 KB Ok
66 Correct 520 ms 8460 KB Ok
67 Correct 624 ms 8448 KB Ok
68 Correct 396 ms 7308 KB Ok
69 Correct 455 ms 8284 KB Ok
70 Correct 449 ms 7796 KB Ok
71 Correct 469 ms 7424 KB Ok
72 Correct 463 ms 7764 KB Ok
73 Correct 528 ms 8700 KB Ok
74 Correct 446 ms 7660 KB Ok
75 Correct 491 ms 8384 KB Ok
76 Correct 507 ms 8172 KB Ok
77 Correct 476 ms 7920 KB Ok
78 Correct 441 ms 7464 KB Ok
79 Correct 424 ms 8224 KB Ok
80 Correct 1053 ms 12552 KB Ok
81 Correct 819 ms 13200 KB Ok
82 Correct 754 ms 12632 KB Ok
83 Correct 760 ms 12588 KB Ok
84 Correct 795 ms 12792 KB Ok
85 Correct 716 ms 12456 KB Ok
86 Correct 790 ms 12568 KB Ok
87 Correct 823 ms 12688 KB Ok
88 Correct 761 ms 12460 KB Ok
89 Correct 767 ms 12600 KB Ok
90 Correct 799 ms 13028 KB Ok
91 Correct 741 ms 12564 KB Ok
92 Correct 746 ms 12800 KB Ok
93 Correct 750 ms 12600 KB Ok
94 Correct 760 ms 12860 KB Ok
95 Correct 1214 ms 23052 KB Ok
96 Correct 1795 ms 30808 KB Ok
97 Correct 1720 ms 25780 KB Ok
98 Correct 1340 ms 26296 KB Ok
99 Correct 1558 ms 24192 KB Ok
100 Correct 1503 ms 25696 KB Ok
101 Correct 1593 ms 27368 KB Ok
102 Correct 1544 ms 25616 KB Ok
103 Correct 1611 ms 28388 KB Ok
104 Correct 1961 ms 29472 KB Ok
105 Correct 1683 ms 30472 KB Ok
106 Correct 1546 ms 28944 KB Ok
107 Correct 1657 ms 28376 KB Ok
108 Correct 1902 ms 30464 KB Ok
109 Correct 1782 ms 30944 KB Ok
110 Execution timed out 2077 ms 30520 KB Time limit exceeded
111 Halted 0 ms 0 KB -