Submission #173966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
173966	2020-01-05T21:56:12 Z	mcdx9524	Nice sequence (IZhO18_sequence)	C++14	Compilation error	0 ms	0 KB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution<int> (l, r) (rng);
}

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 + 1, 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 = rand(l, r);
        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] - p[i - 1] << ' ';
    }
    cout << '\n';
}

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

Compilation message

sequence.cpp: In function 'int rand(int, int)':
sequence.cpp:10:50: error: 'rng' was not declared in this scope
     return uniform_int_distribution<int> (l, r) (rng);
                                                  ^~~
sequence.cpp:10:50: note: suggested alternative: 'rnd'
     return uniform_int_distribution<int> (l, r) (rng);
                                                  ^~~
                                                  rnd