# AGC032E Modulo Pairing

Author: Fanyi Pu

Published: 2020-02-10

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/agc032-e>

AGC032E Modulo Pairing 题解。

给一个长度为 $2n$ 的序列，要求将其两两匹配成 $n$ 组，假设第 $i$ 组为 $(x_i,y_i)$，求 $\max_{i=1}^n(x_i+y_i)\bmod m$ 的最小值，$1\le n\le 10^5,1\le m\le 10^9,0\le a_i<m$。

我们首先我们有：

$$
(x+y)\bmod m=\begin{cases}
x+y&x+y\le m\\
x+y-m&x+y>m
\end{cases}
$$

接下来我们看几种情况：

![按是否取模区分的四种区间配对调整情况](https://pufanyi.com/posts/oi-icpc/atcoder/agc032-e/images/pairing-cases.avif)

如果我们有 $x_1\le x_2\le x_3\le x_4$，那么我们有这样 $4$ 中情况：

第一种，$x_3+x_4<m$，那显然 $(x_1,x_4),(x_2,x_3)$ 更优。

第二种，$x_1+x_2\ge m$，和第一种一样。

第三种，$\begin{cases}x_1+x_3<m\\x_2+x_4\ge m\end{cases}$，考虑到 $x_2+x_4-m<x_2$，故有 $\max\{x_1+x_3,x_2+x_4-m\}=x_1+x_3$，而考虑到 $\begin{cases}x_1+x_2\le x_1+x_3\\x_3+x_4-m<x_3\end{cases}$，故有 $\max\{x_1+x_3,x_2+x_4-m\}\ge \max\{x_1+x_2,x_3+x_4-m\}$。所以 $(x_1,x_2),(x_3,x_4)$ 一定比 $(x_1,x_3),(x_2,x_4)$ 优。

我们再来看 $(x_1,x_4),(x_2,x_3)$ 的情况。如果有 $\begin{cases}x_1+x_4\ge m\\x_2+x_3\ge m\end{cases}$，那就有 $\begin{cases}x_1+x_4-m<x1\\x_2+x_3-m<x_2\end{cases}$，所以 $\max\{x_1+x_4-m,x_2+x_3-m\}<x_2\le \max\{x_1+x_2,x_3+x_4-m\}$，此时 $(x_1,x_4),(x_2,x_3)$ 的方案更优。但是如果有 $x_1+x_4\le m$ 或是 $x_2+x_3\le m$，则答案将会更大。

第四种，$\begin{cases}x_1+x_4<m\\x_2+x_3<m\\x_3+x_6\ge m\\x_4+x_5\ge m\end{cases}$。根据前面的讨论，我们仅需比较 $(x_1,x_4),(x_2,x_3),(x_5,x_6)$ 和 $(x_1,x_2),(x_3,x_4),(x_5,x_6)$ 即可，不难发现 $\begin{cases}x_1+x_2\le x_1+x_4\\x_3+x_6-m<x_3\le x_2+x_3\\x_4+x_5-m\le x_5+x_6-m\end{cases}$，于是 $\max\{x_1+x_2,x_3+x_6-m,x_4+x_5-m\}\le \max\{x_1+x_4,x_2+x_3,x_5+x_6-m\}$。

根据第一、二、三种情况，我们发现，最终的划分结果肯定是被分成两部分，左边部分最小的匹配，次大的和次小的匹配……右边也这样匹配。其中左边所有的匹配 $(x,y)$ 都有 $x+y<m$，右边的匹配 $(x,y)$ 都有 $x+y\ge m$。

根据第四种情况，我们可以发现蓝色的匹配数越多越好，于是我们考虑二分蓝色的匹配数量，最终确定答案。

代码可以看[这里](https://atcoder.jp/contests/agc032/submissions/9683145)。

```cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

namespace pufanyi {

    inline char gc() {
        static const int L = 233333;
        static char sxd[L], *sss = sxd, *ttt = sxd;
        if (sss == ttt) {
            ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
            if (sss == ttt) {
                return EOF;
            }
        }
        return *sss++;
    }

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
    inline char readalpha() {
        char dd;
        for (; !isalpha(c); dd);
        return c;
    }

    inline char readchar() {
        char dd;
        for (; c == ' '; dd);
        return c;
    }

    template <class T>
    inline bool read(T& x) {
        bool flg = false;
        char dd;
        x = 0;
        for (; !isdigit(c); dd) {
            if (c == '-') {
                flg = true;
            } else if(c == EOF) {
                return false;
            }
        }
        for (; isdigit(c); dd) {
            x = (x << 1) + (x << 3) + (c ^ 48);
        }
        if (flg) {
            x = -x;
        }
        return true;
    }
#undef dd

    template <class T>
    inline void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x < 10) {
            putchar(x | 48);
            return;
        }
        write(x / 10);
        putchar((x % 10) | 48);
    }

    template <class T>
    inline void writesp(T x) {
        write(x);
        putchar(' ');
    }

    template <class T>
    inline void writeln(T x) {
        write(x);
        puts("");
    }

    typedef long long LL;

    const int maxn = 200005;

    int n, m;
    int aa[maxn];

    inline bool check(int x) {
        int lim = x << 1;
        for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
            if (aa[l] + aa[r] < m) {
                return false;
            }
        }
        return true;
    }

    int Main() {
        read(n), read(m);
        for (int i = 1; i <= n << 1; ++i) {
            read(aa[i]);
        }
        sort(aa + 1, aa + (n << 1) + 1);
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int ans = 0;
        int lim = l << 1;
        for (int l = 1, r = lim; l < r; ++l, --r) {
            ans = max(ans, (aa[l] + aa[r]) % m);
        }
        for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
            ans = max(ans, (aa[l] + aa[r]) % m);
        }
        writeln(ans);
        return 0;
    }

}

int main() {
    return pufanyi::Main();
}
```