提出 #67007541

---

ソースコード 拡げる

// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <array>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define tisic 47
#define soclose 1e-8
#define patkan 9
#define ff first
#define ss second
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

template <typename T>
T abs(T x) { return (x < 0) ? (-x) : x; }

cat gcd(cat a, cat b) {
	if(a > b) swap(a, b);
	while(a) {
		cat c = b%a;
		b = a;
		a = c;
	}
	return b;
}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? x * a % mod : x;
}

template <typename T>
class fin {
	vector<T> node_val;

	int lastone(int x) { return x & (x ^ (x-1)); }

public:
	fin(int N, T init_val) {
		node_val.resize(N+10, init_val);
	}

	void put(int pos, T val) {
		for(int i = pos+1; i < (int)node_val.size(); i += lastone(i))
			node_val[i] += val;
	}

	T get(int pos) {
		T ret = 0;
		for(int i = pos+1; i > 0; i -= lastone(i))
			ret += node_val[i];
		return ret;
	}
};

constexpr cat MOD = 998244353;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << setprecision(12);
	int T;
	cin >> T;
	while(T--) {
		int N, M;
		cin >> N >> M;
		vector<int> A(N), B(N);
		for(int i = 0; i < N; i++) cin >> A[i];
		for(int i = 0; i < N; i++) cin >> B[i];
		sort(begin(A), end(A));
		sort(begin(B), end(B));
		int ans_lt = -1, ans_ge = M-1;
		while(ans_ge - ans_lt > 1) {
			int m = (ans_lt + ans_ge) / 2;
			bool ok = true;
			int offset = 0, val_offset = -1;
			for(int i = 0; i < N; i++) {
				int val = (A[0] + B[i]) % M;
				if(val > m) continue;
				if(val_offset <= val) val_offset = val, offset = i;
			}
			if(val_offset == -1) ok = false;
			else {
				offset += N;
				for(int i = 0; i < N; i++) {
					while(offset >= 0 && (A[i] + B[(offset-i+N)%N]) % M > m) offset--;
					if(offset < 0) break;
				}
				if(offset < 0) ok = false;
				else for(int i = 0; i < N; i++)
					if((A[i] + B[(offset-i+N)%N]) % M > m) ok = false;
			}
			if(!ok) ans_lt = m;
			else ans_ge = m;
		}
		cout << ans_ge << "\n";
	}
}

// look at my code
// my code is amazing

提出情報

ジャッジ結果