题目详情题解（0）讨论（0）提交记录（0）

AT_arc201_d.[ARC201D] Match, Mod, Minimize

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你两个长度为 NN 的数列 A=(A1,A2,⋯ ,AN),B=(B1,B2,⋯ ,BN)A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N) 和一个正整数 MM，你可以对 AA 重新排序，求 max⁡i=1N((Ai+Bi) mod M)\max_{i=1}^N((A_i+B_i)\bmod M) 的最小值。

多组数据。

输入格式

多组数据。第一行一个整数 T(1≤T≤3×105)T(1\le T \le 3\times 10^5)，表示数据组数。

对于每组数据，第一行两个整数 N,M(1≤N≤3×105,1≤M≤109)N,M(1\le N\le 3\times 10^5,1\le M\le 10^9)。
第二行 NN 个整数 A1,A2,⋯ ,AN(0≤Ai<M)A_1,A_2,\cdots,A_N(0\le A_i<M)。
第三行 NN 个整数 B1,B2,⋯ ,BN(0≤Bi<M)B_1,B_2,\cdots,B_N(0\le B_i<M)。

保证单个测试点内 ∑N≤3×105\sum N\le 3\times 10^5。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例

  • 输入#1

    3
3 6
3 1 4
2 0 1
1 1000000000
999999999
999999999
10 201
144 150 176 154 110 187 38 136 111 46
96 109 73 63 85 1 156 7 13 171

    输出#1

    3
999999998
111

说明/提示

样例 1 解释

对于第一组数据，我们可以重排 AA，令 A=(4,3,1)A=(4,3,1)，(Ai+Bi) mod M(A_i+B_i)\bmod M 依次为 0,3,20,3,2，它们的最大值为 33。

By @chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页