Submission #1204822

#TimeUsernameProblemLanguageResultExecution timeMemory
1204822LucaIlieGrowing Vegetables is Fun 5 (JOI24_vegetables5)C++20
9 / 100
5094 ms13080 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...