Submission #1128685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128685		_callmelucian	Nice sequence (IZhO18_sequence)	C++17	0 / 100	19 ms	28592 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;

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; scanf("%d %d", &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)

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

    graph::resetGraph(sz);
}

signed main()
{
    int TC; scanf("%d", &TC);
    while (TC--) solve();

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:102:23: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  102 |     int n, m; scanf("%d %d", &n, &m);
      |                      ~^      ~~
      |                       |      |
      |                       int*   long long int*
      |                      %lld
sequence.cpp:102:26: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
  102 |     int n, m; scanf("%d %d", &n, &m);
      |                         ~^       ~~
      |                          |       |
      |                          int*    long long int*
      |                         %lld
sequence.cpp:118:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  118 |     printf("%d\n", ans);
      |             ~^     ~~~
      |              |     |
      |              int   long long int
      |             %lld
sequence.cpp:120:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  120 |         printf("%d ", (curConstruct[i] - curConstruct[i - 1]) * (swapped ? -1 : 1));
      |                 ~^    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                  |                                            |
      |                  int                                          long long int
      |                 %lld
sequence.cpp: In function 'int main()':
sequence.cpp:128:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  128 |     int TC; scanf("%d", &TC);
      |                    ~^   ~~~
      |                     |   |
      |                     |   long long int*
      |                     int*
      |                    %lld
sequence.cpp: In function 'void solve()':
sequence.cpp:102:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     int TC; scanf("%d", &TC);
      |             ~~~~~^~~~~~~~~~~

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