Submission #173969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
173969	2020-01-05T22:02:29 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) (rnd);
}

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, bool kek) {
    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;
        }
    }
    if (!kek) return true;
    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 = n + m - 1 - gcd(n, m);
    /*
    while (l <= r) {
        int md = rand(l, r);
        if (build(md, 0)) {
            l = md + 1;
            ans = md;
        } else {
            r = md - 1;
        }
    }
    /*
    build(ans, 1);
    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:103:5: warning: "/*" within comment [-Wcomment]
     /*
      
sequence.cpp:93:5: error: unterminated comment
     /*
     ^
sequence.cpp: In function 'void solve()':
sequence.cpp:92:27: error: 'gcd' was not declared in this scope
     int ans = n + m - 1 - gcd(n, m);
                           ^~~
sequence.cpp:91:9: warning: unused variable 'l' [-Wunused-variable]
     int l = max(n, m) - 1, r = n + m + 7;
         ^
sequence.cpp:91:28: warning: unused variable 'r' [-Wunused-variable]
     int l = max(n, m) - 1, r = n + m + 7;
                            ^
sequence.cpp:92:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans = n + m - 1 - gcd(n, m);
         ^~~
sequence.cpp:92:36: error: expected '}' at end of input
     int ans = n + m - 1 - gcd(n, m);
                                    ^