Overview

Each presenter chooses their start time from \(2\) options. For given \(M\) pairs, we want to maximize the minimum difference in start times. We need to find this maximum value \(K\) and the lexicographically smallest choice that achieves it.

Analysis

Let the choice of each presenter \(i\) be a variable \(X_i \in \{0,1\}\).

• If \(X_i=0\), the start time is \(A_i\).
• If \(X_i=1\), the start time is \(A_i+D_i\).

For a certain value \(k\), if we can determine:

Can the difference between start times be at least \(k\) for all specified pairs \((u,v)\)?

then we can find \(K\) using binary search.

This is because if a certain \(k\) is achievable, any value smaller than \(k\) is also achievable.
Conversely, if a certain \(k\) is unachievable, any value larger than \(k\) is also unachievable.

In other words, the feasibility has monotonicity.

---

Feasibility check can be formulated as 2-SAT

Let’s focus on a pair \((u,v)\).

We precompute the difference in start times when we choose \(X_u=a\) and \(X_v=b\).

If this difference is less than \(k\), this combination cannot be used.

That is,

\[ X_u=a \land X_v=b \]

is forbidden.

This can be rewritten as:

\[ \neg(X_u=a \land X_v=b) \]

\[ \equiv (X_u \neq a) \lor (X_v \neq b) \]

This is a clause in 2-SAT.

For example, if \(X_u=0, X_v=1\) is forbidden, the constraint is:

\[ (X_u \neq 0) \lor (X_v \neq 1) \]

which is:

\[ (X_u=1) \lor (X_v=0) \]

In 2-SAT, we convert a clause

\[ P \lor Q \]

into the following implications:

\[ \neg P \Rightarrow Q \]

\[ \neg Q \Rightarrow P \]

In our case, for the forbidden condition

\[ (X_u=a) \land (X_v=b) \]

we add the edges:

\[ (X_u=a) \Rightarrow (X_v \neq b) \]

\[ (X_v=b) \Rightarrow (X_u \neq a) \]

In this implication graph, if there exists a variable \(X_i\) such that \(X_i=0\) and \(X_i=1\) belong to the same strongly connected component, it is impossible due to a contradiction.

---

Finding the lexicographically smallest string

After finding the maximum value \(K\), we can determine the lexicographically smallest \(S\) greedily.

We iterate from left to right. For each position \(i\), we first try to fix \(S_i=0\).

• If it is possible to achieve \(f(S)=K\) under this condition, we set \(S_i=0\).
• Otherwise, we set \(S_i=1\).

Since 0 is smaller than 1 lexicographically, greedily choosing 0 as much as possible from left to right yields the lexicographically smallest string.

The fixing condition \(S_i=c\) can also be added to the 2-SAT instance.
This is a unit clause \(X_i=c\), which can be represented in the implication graph by adding the edge:

\[ X_i \neq c \Rightarrow X_i=c \]

Algorithm

1. For each pair \((u,v)\), precompute the start time differences for all \(4\) combinations of \(X_u, X_v\).
2. Implement a function feasible(k) that checks if a certain \(k\) is achievable.
   • For each pair, forbid the combinations of choices where the start time difference is less than \(k\).
   • Convert the forbidden conditions into a 2-SAT implication graph.
   • Perform strongly connected component (SCC) decomposition and check if \(0\) and \(1\) for each variable are in the same component.
3. Binary search on \(k\) to find the maximum achievable value \(K\).
4. Fix \(K\) and construct the string from left to right.
   • First, try fixing to 0 and run the 2-SAT check.
   • If feasible, choose 0; otherwise, choose 1.
5. Output \(K\) and the resulting string.

Complexity

Let \(C\) be the upper bound of the maximum start time difference. Here, \(C \leq 2 \times 10^9\).

In a single 2-SAT check, the number of vertices is \(2N\), and the number of edges is at most \(O(M+N)\).
Therefore, a single check takes \(O(N+M)\) time.

Since we run the check \(O(\log C)\) times during the binary search, and \(N\) times to construct the lexicographically smallest string:

• Time Complexity: \(O((N+\log C)(N+M))\)
• Space Complexity: \(O(N+M)\)

Implementation Details

• The literals of each variable \(X_i\) can be represented as follows:

  • (i << 1) | 0 : \(X_i=0\)
  • (i << 1) | 1 : \(X_i=1\)

• The negation of a literal can be obtained by ^ 1.

  • The negation of \(X_i=0\) is \(X_i=1\)
  • The negation of \(X_i=1\) is \(X_i=0\)

• Since the times can be up to \(2 \times 10^9\), it is safe to use long long.

• Strongly connected component decomposition is used for the 2-SAT check. In this code, it is implemented using Tarjan’s algorithm.

  Source Code

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

struct Constraint {
    int u, v;
    long long diff[2][2];
};

struct TwoSatChecker {
    int n, V;
    vector<Constraint> cons;

    vector<int> head, to, nxt;
    vector<int> disc, low, comp, st;
    vector<unsigned char> in_st;
    int timer, comp_cnt;

    TwoSatChecker(int n_, vector<Constraint>&& cons_)
        : n(n_), V(2 * n_), cons(move(cons_)),
          head(V, -1), disc(V), low(V), comp(V), in_st(V) {
        size_t cap = 8ULL * cons.size() + n + 10;
        to.reserve(cap);
        nxt.reserve(cap);
        st.reserve(V);
    }

    inline void add_edge(int a, int b) {
        nxt.push_back(head[a]);
        to.push_back(b);
        head[a] = (int)to.size() - 1;
    }

    void dfs(int v) {
        disc[v] = low[v] = ++timer;
        st.push_back(v);
        in_st[v] = 1;

        for (int e = head[v]; e != -1; e = nxt[e]) {
            int w = to[e];
            if (!disc[w]) {
                dfs(w);
                low[v] = min(low[v], low[w]);
            } else if (in_st[w]) {
                low[v] = min(low[v], disc[w]);
            }
        }

        if (low[v] == disc[v]) {
            while (true) {
                int w = st.back();
                st.pop_back();
                in_st[w] = 0;
                comp[w] = comp_cnt;
                if (w == v) break;
            }
            comp_cnt++;
        }
    }

    bool feasible(long long k, const vector<int>* fixed = nullptr) {
        fill(head.begin(), head.end(), -1);
        to.clear();
        nxt.clear();

        for (const auto& c : cons) {
            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    if (c.diff[a][b] < k) {
                        int p = (c.u << 1) | a;
                        int q = (c.v << 1) | b;
                        add_edge(p, q ^ 1);
                        add_edge(q, p ^ 1);
                    }
                }
            }
        }

        if (fixed) {
            for (int i = 0; i < n; i++) {
                if ((*fixed)[i] != -1) {
                    int lit = (i << 1) | (*fixed)[i];
                    add_edge(lit ^ 1, lit);
                }
            }
        }

        fill(disc.begin(), disc.end(), 0);
        fill(comp.begin(), comp.end(), -1);
        fill(in_st.begin(), in_st.end(), 0);
        st.clear();
        timer = 0;
        comp_cnt = 0;

        for (int i = 0; i < V; i++) {
            if (!disc[i]) dfs(i);
        }

        for (int i = 0; i < n; i++) {
            if (comp[i << 1] == comp[(i << 1) | 1]) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> A(N), D(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> D[i];
    }

    vector<Constraint> cons;
    cons.reserve(M);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;

        Constraint c;
        c.u = u;
        c.v = v;

        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                long long tu = A[u] + (a ? D[u] : 0);
                long long tv = A[v] + (b ? D[v] : 0);
                c.diff[a][b] = abs(tu - tv);
            }
        }

        cons.push_back(c);
    }

    if (M == 0) {
        cout << 0 << '\n' << string(N, '0') << '\n';
        return 0;
    }

    TwoSatChecker checker(N, move(cons));

    long long ok = 0, ng = 2000000001LL;
    while (ng - ok > 1) {
        long long mid = (ok + ng) / 2;
        if (checker.feasible(mid)) ok = mid;
        else ng = mid;
    }

    vector<int> fixed(N, -1);
    string ans(N, '0');

    for (int i = 0; i < N; i++) {
        fixed[i] = 0;
        if (checker.feasible(ok, &fixed)) {
            ans[i] = '0';
        } else {
            fixed[i] = 1;
            ans[i] = '1';
        }
    }

    cout << ok << '\n' << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.