제출 #1157133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157133		dubabuba	Room Temperature (JOI24_ho_t1)	C++20	35 / 100	1 ms	396 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 5e5 + 10;
int a[mxn], r[mxn], n, t;

bool can(int d) {
	vector<pii> vec;
	for(int i = 1; i <= n; i++) {
		int l = ::r[i] - d;
		int r = ::r[i] + d;

		if(l < 0) {
			l += t;
			r += t;
		}

		vec.push_back(MP(l, r));
	}

	sort(vec.begin(), vec.end());
	for(int i = 1; i <= n; i++) {
		if(vec[i - 1].ss < vec[i].ff)
			return false;
	}
	return true;
}

int main() {
	cin >> n >> t;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		r[i] = a[i] % t;
	}

	bool sus = true;
	for(int i = 2; i <= n; i++)
		if(r[i - 1] != r[i])
			sus = false;

	if(sus) {
		cout << 0 << endl;
		return 0;
	}

	int L = 0, R = t;
	while(R - L > 1) {
		int M = (L + R) / 2;
		if(can(M)) R = M;
		else L = M;
	}

	if(R == 0) return 1;
	if(t < 2 * R) return 1;
	cout << R << endl;
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 15