oj.uz

Submission #689404

# Submission time Handle Problem Language Result Execution time Memory
689404 2023-01-28T12:16:19 Z gesgha Nice sequence (IZhO18_sequence) C++17
6 / 100
 1 ms 340 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) {
    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 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[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) - 1;

    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 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 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Jury has the better answer : jans = 3, pans = 2
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Incorrect 0 ms 340 KB Jury has the better answer : jans = 5, pans = 4
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Jury has the better answer : jans = 5, pans = 3
2 Halted 0 ms 0 KB -

Subtask #5
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 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 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Incorrect 0 ms 340 KB Jury has the better answer : jans = 5, pans = 4
16 Halted 0 ms 0 KB -

Subtask #6
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 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 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Incorrect 0 ms 340 KB Jury has the better answer : jans = 3, pans = 2
14 Halted 0 ms 0 KB -

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 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 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Incorrect 0 ms 340 KB Jury has the better answer : jans = 3, pans = 2
14 Halted 0 ms 0 KB -