oj.uz

Submission #689412

# Submission time Handle Problem Language Result Execution time Memory
689412 2023-01-28T12:38:50 Z gesgha Nice sequence (IZhO18_sequence) C++17
100 / 100
 1043 ms 48404 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];
int n, m, k;


void dfs(int v) {
    vis[v] = 1;
    
    if (v + m <= k && !vis[v + m]) dfs(v + m);
    if (v - n >= 0 && !vis[v - n]) dfs(v - n);
    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;
    if (v + m <= k) {
        if (visn[v + m]) return 1;
        if (!vis[v + m]) {
            ok |= is_cycle(v + m);
            if (ok) return 1;
        }
    }
    if (v - n >= 0) {
        if (visn[v - n]) return 1;
        if (!vis[v - n]) {
            ok |= is_cycle(v - n);
            if (ok) return 1;
        }
    }
    return 0;
}


bool can(int n, int m, int k) {
    ::n = n;
    ::m = m;
    ::k = 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;
    }
    ::k = l;
    ::n = n;
    ::m = m;

    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 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 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 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 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 2 ms 468 KB Ok
7 Correct 11 ms 1332 KB Ok
8 Correct 4 ms 724 KB Ok
9 Correct 10 ms 1492 KB Ok
10 Correct 6 ms 980 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 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 0 ms 340 KB Ok
8 Correct 0 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 0 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 178 ms 12164 KB Ok
7 Correct 135 ms 11356 KB Ok
8 Correct 293 ms 14364 KB Ok
9 Correct 205 ms 13604 KB Ok
10 Correct 136 ms 8512 KB Ok
11 Correct 203 ms 15476 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 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 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 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 0 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 0 ms 340 KB Ok
20 Correct 0 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 2 ms 468 KB Ok
25 Correct 2 ms 468 KB Ok
26 Correct 2 ms 468 KB Ok
27 Correct 2 ms 468 KB Ok
28 Correct 2 ms 468 KB Ok
29 Correct 2 ms 468 KB Ok
30 Correct 3 ms 340 KB Ok
31 Correct 3 ms 468 KB Ok
32 Correct 3 ms 468 KB Ok
33 Correct 4 ms 468 KB Ok
34 Correct 8 ms 624 KB Ok
35 Correct 5 ms 596 KB Ok
36 Correct 6 ms 668 KB Ok
37 Correct 6 ms 648 KB Ok
38 Correct 6 ms 640 KB Ok
39 Correct 5 ms 596 KB Ok
40 Correct 6 ms 596 KB Ok
41 Correct 6 ms 596 KB Ok
42 Correct 6 ms 596 KB Ok
43 Correct 6 ms 596 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 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 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 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 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 2 ms 468 KB Ok
19 Correct 11 ms 1332 KB Ok
20 Correct 4 ms 724 KB Ok
21 Correct 10 ms 1492 KB Ok
22 Correct 6 ms 980 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 0 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 0 ms 340 KB Ok
30 Correct 0 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 2 ms 468 KB Ok
35 Correct 2 ms 468 KB Ok
36 Correct 2 ms 468 KB Ok
37 Correct 2 ms 468 KB Ok
38 Correct 2 ms 468 KB Ok
39 Correct 2 ms 468 KB Ok
40 Correct 3 ms 340 KB Ok
41 Correct 3 ms 468 KB Ok
42 Correct 3 ms 468 KB Ok
43 Correct 4 ms 468 KB Ok
44 Correct 8 ms 624 KB Ok
45 Correct 5 ms 596 KB Ok
46 Correct 6 ms 668 KB Ok
47 Correct 6 ms 648 KB Ok
48 Correct 6 ms 640 KB Ok
49 Correct 5 ms 596 KB Ok
50 Correct 6 ms 596 KB Ok
51 Correct 6 ms 596 KB Ok
52 Correct 6 ms 596 KB Ok
53 Correct 6 ms 596 KB Ok
54 Correct 121 ms 4396 KB Ok
55 Correct 121 ms 4836 KB Ok
56 Correct 119 ms 4844 KB Ok
57 Correct 80 ms 3916 KB Ok
58 Correct 101 ms 4728 KB Ok
59 Correct 105 ms 4452 KB Ok
60 Correct 78 ms 4040 KB Ok
61 Correct 91 ms 4220 KB Ok
62 Correct 133 ms 5088 KB Ok
63 Correct 90 ms 4268 KB Ok
64 Correct 116 ms 4792 KB Ok
65 Correct 117 ms 4848 KB Ok
66 Correct 91 ms 4348 KB Ok
67 Correct 81 ms 4112 KB Ok
68 Correct 106 ms 4640 KB Ok
69 Correct 228 ms 11596 KB Ok
70 Correct 230 ms 11832 KB Ok
71 Correct 222 ms 11020 KB Ok
72 Correct 227 ms 11596 KB Ok
73 Correct 212 ms 11160 KB Ok
74 Correct 201 ms 10952 KB Ok
75 Correct 225 ms 11312 KB Ok
76 Correct 214 ms 11628 KB Ok
77 Correct 223 ms 10860 KB Ok
78 Correct 224 ms 11552 KB Ok
79 Correct 293 ms 11180 KB Ok
80 Correct 204 ms 10828 KB Ok
81 Correct 216 ms 11568 KB Ok
82 Correct 222 ms 10960 KB Ok
83 Correct 213 ms 11724 KB Ok

Subtask #7
24.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 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 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 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 0 ms 340 KB Ok
16 Correct 1 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 2 ms 468 KB Ok
19 Correct 11 ms 1332 KB Ok
20 Correct 4 ms 724 KB Ok
21 Correct 10 ms 1492 KB Ok
22 Correct 6 ms 980 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 0 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 0 ms 340 KB Ok
30 Correct 0 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 0 ms 340 KB Ok
37 Correct 1 ms 340 KB Ok
38 Correct 1 ms 340 KB Ok
39 Correct 178 ms 12164 KB Ok
40 Correct 135 ms 11356 KB Ok
41 Correct 293 ms 14364 KB Ok
42 Correct 205 ms 13604 KB Ok
43 Correct 136 ms 8512 KB Ok
44 Correct 203 ms 15476 KB Ok
45 Correct 2 ms 468 KB Ok
46 Correct 2 ms 468 KB Ok
47 Correct 2 ms 468 KB Ok
48 Correct 2 ms 468 KB Ok
49 Correct 2 ms 468 KB Ok
50 Correct 2 ms 468 KB Ok
51 Correct 3 ms 340 KB Ok
52 Correct 3 ms 468 KB Ok
53 Correct 3 ms 468 KB Ok
54 Correct 4 ms 468 KB Ok
55 Correct 8 ms 624 KB Ok
56 Correct 5 ms 596 KB Ok
57 Correct 6 ms 668 KB Ok
58 Correct 6 ms 648 KB Ok
59 Correct 6 ms 640 KB Ok
60 Correct 5 ms 596 KB Ok
61 Correct 6 ms 596 KB Ok
62 Correct 6 ms 596 KB Ok
63 Correct 6 ms 596 KB Ok
64 Correct 6 ms 596 KB Ok
65 Correct 121 ms 4396 KB Ok
66 Correct 121 ms 4836 KB Ok
67 Correct 119 ms 4844 KB Ok
68 Correct 80 ms 3916 KB Ok
69 Correct 101 ms 4728 KB Ok
70 Correct 105 ms 4452 KB Ok
71 Correct 78 ms 4040 KB Ok
72 Correct 91 ms 4220 KB Ok
73 Correct 133 ms 5088 KB Ok
74 Correct 90 ms 4268 KB Ok
75 Correct 116 ms 4792 KB Ok
76 Correct 117 ms 4848 KB Ok
77 Correct 91 ms 4348 KB Ok
78 Correct 81 ms 4112 KB Ok
79 Correct 106 ms 4640 KB Ok
80 Correct 228 ms 11596 KB Ok
81 Correct 230 ms 11832 KB Ok
82 Correct 222 ms 11020 KB Ok
83 Correct 227 ms 11596 KB Ok
84 Correct 212 ms 11160 KB Ok
85 Correct 201 ms 10952 KB Ok
86 Correct 225 ms 11312 KB Ok
87 Correct 214 ms 11628 KB Ok
88 Correct 223 ms 10860 KB Ok
89 Correct 224 ms 11552 KB Ok
90 Correct 293 ms 11180 KB Ok
91 Correct 204 ms 10828 KB Ok
92 Correct 216 ms 11568 KB Ok
93 Correct 222 ms 10960 KB Ok
94 Correct 213 ms 11724 KB Ok
95 Correct 257 ms 11260 KB Ok
96 Correct 353 ms 16388 KB Ok
97 Correct 398 ms 14096 KB Ok
98 Correct 254 ms 12992 KB Ok
99 Correct 296 ms 13144 KB Ok
100 Correct 388 ms 13772 KB Ok
101 Correct 379 ms 14512 KB Ok
102 Correct 337 ms 13944 KB Ok
103 Correct 337 ms 14596 KB Ok
104 Correct 379 ms 15912 KB Ok
105 Correct 402 ms 16072 KB Ok
106 Correct 291 ms 14912 KB Ok
107 Correct 351 ms 15228 KB Ok
108 Correct 406 ms 16412 KB Ok
109 Correct 348 ms 15900 KB Ok
110 Correct 912 ms 47392 KB Ok
111 Correct 1035 ms 48376 KB Ok
112 Correct 963 ms 46460 KB Ok
113 Correct 971 ms 47420 KB Ok
114 Correct 993 ms 47068 KB Ok
115 Correct 1020 ms 48404 KB Ok
116 Correct 1018 ms 47888 KB Ok
117 Correct 927 ms 48028 KB Ok
118 Correct 999 ms 46828 KB Ok
119 Correct 1018 ms 47364 KB Ok
120 Correct 999 ms 48220 KB Ok
121 Correct 921 ms 45796 KB Ok
122 Correct 958 ms 48388 KB Ok
123 Correct 984 ms 46296 KB Ok
124 Correct 985 ms 46876 KB Ok
125 Correct 1043 ms 31688 KB Ok