Submission #1128678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128678		_callmelucian	Nice sequence (IZhO18_sequence)	C++17	23 / 100	270 ms	62848 KiB

sequence

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

#define int long long

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 resetGraph (int n) {
        fill(num, num + n + 1, 0);
        fill(low, low + n + 1, 0);
        fill(del, del + n + 1, 0);
//        for (int i = 0; i <= n; i++)
//            adj[i].clear(), rev[i].clear();
        while (st.size()) st.pop();
        timeDfs = containCycle = 0, topo.clear();
    }

    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 lo[mn], hi[mn], curConstruct[mn];

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll rr (ll L, ll R) {
    return uniform_int_distribution<ll>(L, R)(rng);
}

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

    // construct possible answer
    for (int u : graph::topo) {
        curConstruct[u] = rr(0, M);
        for (int v : graph::rev[u])
            if (v <= sz) curConstruct[u] = max(curConstruct[u], curConstruct[v] + rr(1, M));
    }
    graph::resetGraph(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";

    for (int i = 0; i <= sz; i++)
        graph::adj[i].clear(), graph::rev[i].clear();
}

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

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

    return 0;
}

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