oj.uz

Submission #173961

# Submission time Handle Problem Language Result Execution time Memory
173961 2020-01-05T21:43:06 Z mcdx9524 Nice sequence (IZhO18_sequence) C++14
0 / 100
 76 ms 29668 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 7;

int n, m;
vector <int> p;
vector <int> ord;
vector <int> g[N];
bool used[N];
int col[N];

bool cycle(int v) {
    col[v] = 1;
    for (int u : g[v]) {
        if (col[u] == 0) {
            if (cycle(u)) {
                return true;
            }
        } else if (col[u] == 1) {
            return true;
        }
    }
    col[v] = 2;
    return false;
}

void dfs(int v) {
    if (used[v] == true) {
        return;
    }
    used[v] = true;
    for (int u : g[v]) {
        dfs(u);
    }
    ord.push_back(v);
}

bool build(int sz) {
    ord.clear();
    for (int i = 0; i < N; i++) {
        g[i].clear();
        used[i] = false;
        col[i] = 0;
    }
    for (int i = 1; i <= sz; i++) {
        // p[i] - p[i - n] < 0
        // p[i] < p[i - n]
        if (i - n >= 0) {
            g[i - n].push_back(i);
        }
        // p[i] > p[i - m]
        if (i - m >= 0) {
            g[i].push_back(i - m);
        }
    }
    for (int i = 0; i <= sz; i++) {
        if (cycle(i)) {
            return false;
        }
    }
    for (int i = 0; i <= sz; i++) {
        dfs(i);
    }
    p.resize(sz, 0);
    int cur = sz;
    reverse(ord.begin(), ord.end());
    for (int x : ord) {
        p[x] = cur--;
    }
    for (int i = 0; i <= sz; i++) {
        if (!p[i]) {
            p[i] = cur--;
        }
    }
    return true;
}

void solve() {
    cin >> n >> m;
    int l = max(n, m) - 1, r = n + m + 7;
    int ans = l;
    while (l <= r) {
        int md = (l + r) / 2;
        if (build(md)) {
            l = md + 1;
            ans = md;
        } else {
            r = md - 1;
        }
    }
    build(ans);
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++) {
        cout << p[i] - (i == 0 ? 0 : p[i - 1]) << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 14584 KB Ok
2 Correct 75 ms 14456 KB Ok
3 Correct 76 ms 14584 KB Ok
4 Correct 75 ms 14456 KB Ok
5 Correct 76 ms 14584 KB Ok
6 Runtime error 40 ms 29668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14604 KB Ok
2 Runtime error 41 ms 29336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 29424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -