AGC 032 E. Modulo Pairing

E - Modulo Pairing

まず $mod\ M$ の制約を無視して考えると，数直線状で交差する二つのペアや独立したペアをとっても得することはないのでペアをすべて入れ子状にしたものが最適解の一つになります．元の問題でこれが成り立つのはいずれのペアも $x + y < m$ であるか $x + y >= m$ であるかのどちらかなのでペアをこの $2$ 種類に分けるとよさそうで，種類の異なる二つのペアの関係は $x + y - (y + Y - m) > 0$ などから左右に独立に切り離せることがわかって，以上の操作を繰り返すと左右に入れ子状のペアが並んだ形に帰着されるので，あとは適当な探索によってこの境界を決定できて，解けました

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; (i) < (int) (n); (i) ++)
using namespace std;

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<int> a(2 * n);
        rep(i, 2 * n) scanf("%d", &a[i]);
        sort(a.begin(), a.end());
        int lb = -1, ub = n;
        while (ub - lb > 1) {
                int mid = (ub + lb) / 2;
                bool ok = true;
                mid *= 2;
                for (int i = mid; i < mid + (2 * n - mid) / 2; i ++) {
                        if (a[i] + a[2 * n + mid - i - 1] < m) {
                                ok = false;
                                break;
                        }
                }
                if (ok) ub = mid / 2;
                else lb = mid / 2;
        }
        int b = ub * 2;
        int ma = 0;
        for (int i = 0; i < b / 2; i ++) ma = max(ma, a[i] + a[b - 1 - i]);
        for (int i = b; i < b + (2 * n - b) / 2; i ++) ma = max(ma, (a[i] + a[2 * n + b - i - 1]) % m);
        printf("%d\n", ma);
        return 0;
}