Submission #1128687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128687		_callmelucian	Nice sequence (IZhO18_sequence)	C++17	58 / 100	2097 ms	66860 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 6e5 + 5;
const int M = 1000;

namespace graph {
    vector<int> adj[mn], rev[mn], topo;
    stack<int> st;

    int num[mn], low[mn], timeDfs;
    bool del[mn], containCycle;

    void dfs (int u, int lim) {
        num[u] = low[u] = ++timeDfs;
        st.push(u);
        for (int v : adj[u]) {
            if (del[v] || v > lim) continue;
            if (!num[v])
                dfs(v, lim), low[u] = min(low[u], low[v]);
            else low[u] = min(low[u], num[v]);
        }

        if (num[u] == low[u]) {
            int cur = 0, sz = 0;
            do {
                cur = st.top(); st.pop();
                del[cur] = 1, sz++;
            } while (cur != u);
            if (sz > 1) containCycle = 1;
            topo.push_back(u);
        }
    }

    void resetData (int n) {
        fill(num, num + n + 1, 0);
        fill(low, low + n + 1, 0);
        fill(del, del + n + 1, 0);
        while (st.size()) st.pop();
        timeDfs = containCycle = 0, topo.clear();
    }

    void resetGraph (int n) {
        for (int i = 0; i <= n; i++)
            adj[i].clear(), rev[i].clear();
        resetData(n);
    }

    bool detectCycle (int n) {
        for (int i = 1; i <= n; i++)
            if (!num[i]) dfs(i, n);
        if (containCycle) return 1;
        return reverse(all(topo)), 0;
    }

    void addEdge (int a, int b) {
        adj[a].push_back(b);
        rev[b].push_back(a);
    }
};

int curConstruct[mn];

bool ok (int sz, int n, int m, bool constructing) {
    if (graph::detectCycle(sz)) return graph::resetData(sz), 0;
    if (!constructing) return graph::resetData(sz), 1;

    // compute each node's level
    for (int u : graph::topo) {
        curConstruct[u] = 0;
        for (int v : graph::rev[u])
            curConstruct[u] = max(curConstruct[u], curConstruct[v] + 1);
    }
    for (int i = 1; i <= sz; i++) {
        if (curConstruct[i - 1] < curConstruct[i]) graph::addEdge(i - 1, i);
        else graph::addEdge(i, i - 1);
    }
    graph::resetData(sz);
    graph::detectCycle(sz);

    // construct solution
    for (int u : graph::topo) {
        curConstruct[u] = 0;
        for (int v : graph::rev[u])
            curConstruct[u] = max(curConstruct[u], curConstruct[v] + 1);
    }
    graph::resetData(sz);
    return 1;
}

void solve() {
    int n, m; cin >> n >> m;
    bool swapped = 0;
    if (n < m) swapped = 1, swap(n, m);
    int sz = (n << 1);

    for (int i = 0; i <= sz; i++) {
        if (i + m <= sz) graph::addEdge(i, i + m);
        if (i + n <= sz) graph::addEdge(i + n, i);
    }

    int ans = 0;
    for (int mask = 1 << 18; mask > 0; mask >>= 1) {
        if ((ans | mask) <= sz && ok(ans | mask, n, m, 0)) ans |= mask;
    }
    ok(ans, n, m, 1); // retrieve information (in case last binary search round is failed)

    cout << ans << "\n";
    for (int i = 1; i <= ans; i++)
        cout << (curConstruct[i] - curConstruct[i - 1]) * (swapped ? -1 : 1) << " ";
    cout << "\n";

    graph::resetGraph(sz);
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int TC; cin >> TC;
    while (TC--) solve();

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24