Submission #4672795

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;

const int N = 800228;
int a[N];
int s[N];

int lc[N];
int rc[N];

set<int> ss;

int n, m;
void dfs(int v) {
    v %= n;
    ss.erase(v);
    ss.erase(v + n);

    for (;;) {
        auto it = ss.lower_bound(lc[v]);
        if (it != ss.end() && *it < rc[v]) {
            dfs(*it % n);
        } else {
            break;
        }
    }
}

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif  
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
 
    cin >> n >> m;
    n *= 2;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);


    for (int i = 0; i < n; ++i) {
        a[n + i] = a[i] + m;
    }

    int l = 0, r = m;


    while (l +1 <r) {
        int md = (l + r) / 2;

        memset(s, 0, sizeof(s));

        /*for (int i = 0; i < 2 * n; ++i) {
            ss.insert(i);
        }*/

        for (int i = 0; i < n; ++i) {
            lc[i] = lower_bound(a, a + 2 * n, m - a[i]) - a;
            rc[i] = lower_bound(a, a + 2 * n, m - a[i] + md) - a;
            ++s[lc[i] + i];
            --s[rc[i] + i];
        }

        bool bad = false;

        /*for (int i = 0; i < n; ++i) {
            if (ss.count(i)) {
                dfs(i);

                bad |= (ss.size() / 2) % 2;
            }
        }*/

        bool good = false;
        for (int i = 0; i < 3 * n; ++i) {
            s[i + 1] += s[i];
        }

        for (int i= 0; i < n; ++i) {
            good |= (i %2) && (s[i] + s[i + n] + s[i + 2 * n] == n);
        }

        ((good && !bad) ? r : l) = md;
    }

    cout << l << "\n";
}

Submission Info

Judge Result