#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5;
const int MAX_VAL = 1e9;
int n;
int a[2 * MAX_N + 1], b[MAX_N + 1], c[MAX_N + 1];
int leftPos[2 * MAX_N + 1], rightPos[2 * MAX_N + 1];
bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1];
bool checkMatch() {
bool isMatch = false;
for (int s = 1; s <= 2 * n; s++) {
int t = s + n;
if (t > 2 * n)
t -= 2 * n;
// printf("%d %d %d %d\n", s, t, startB[s], startC[t]);
isMatch |= (startB[s] & startC[t]);
}
// printf("%d\n", isMatch);
return isMatch;
}
void checkPositionsForColor(int d, int b[], bool start[]) {
int j;
// printf("FAC %d\n", d);
j = 0;
for (int i = 1; i <= n; i++) {
while (j + 1 <= n && b[j + 1] <= a[i] + d)
j++;
rightPos[i] = j;
}
j = 0;
for (int i = 2 * n; i >= n + 1; i--) {
while (j + 1 <= n && b[j + 1] <= a[i] + d)
j++;
rightPos[i] = j;
}
j = 1;
for (int i = 1; i <= n; i++) {
while (j <= n && b[j] < a[i] - d)
j++;
leftPos[i] = j;
}
j = 1;
for (int i = 2 * n; i >= n + 1; i--) {
while (j <= n && b[j] < a[i] - d)
j++;
leftPos[i] = j;
}
// for (int i = 1; i <= 2 * n; i++)
// printf("%d %d\n", leftPos[i], rightPos[i]);
// printf("\n");
//
for (int s = 1; s <= 2 * n; s++) {
vector<int> pos;
for (int i = 0; i < n; i++)
pos.push_back((s + i - 1) % (2 * n) + 1);
sort(pos.begin(), pos.end(), [](int i, int j) {return a[i] < a[j];});
start[s] = true;
for (int i = 0; i < n; i++)
start[s] &= (leftPos[pos[i]] <= i + 1 && i + 1 <= rightPos[pos[i]]);
// printf("%d ", start[s]);
}
// printf("\n");
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= 2 * n; i++)
cin >> a[i];
b[0] = -MAX_VAL;
for (int i = 1; i <= n; i++)
cin >> b[i];
sort(b + 1, b + 1 + n);
c[0] = -MAX_VAL;
for (int i = 1; i <= n; i++)
cin >> c[i];
sort(c + 1, c + 1 + n);
// for (int i = 1; i <= n; i++)
// printf("%d ", b[i]);
// printf("\n");
// for (int i = 1; i <= n; i++)
// printf("%d ", c[i]);
// printf("\n");
int l = -1, r = MAX_VAL;
while (r - l > 1) {
int d = (l + r) / 2;
checkPositionsForColor(d, b, startB);
checkPositionsForColor(d, c, startC);
if (checkMatch())
r = d;
else
l = d;
// printf("\n\n\n");
// printf("\n\n\n");
// printf("\n\n\n");
}
cout << r << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |