-
Notifications
You must be signed in to change notification settings - Fork 23
/
B.cpp
executable file
·60 lines (52 loc) · 1.15 KB
/
B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long dislodging_logs(int N, int M, vector<int>& P, vector<int>& Q) {
int mid, low = 1, high = 1e9;
// preprocess
sort(P.begin(), P.end());
sort(Q.begin(), Q.end());
// helper function
auto good = [&](int x) {
for (int i = 0, r = 0; i < N; i++) {
int l = r;
while (r < M && min(abs(P[i] - Q[l]), abs(P[i] - Q[r])) + Q[r] - Q[l] <= x)
r++;
if (r == M)
return true;
}
return false;
};
// binary search
while (low < high) {
mid = low + (high - low) / 2;
if (good(mid))
high = mid;
else
low = mid + 1;
}
return high;
}
void read_sequence(int K, vector<int>& arr) {
long long A, B, C, D;
for (int i = 0; i < K; i++)
cin >> arr[i];
cin >> A >> B >> C >> D;
for (int i = K; i < arr.size(); i++)
arr[i] = (A * arr[i - 2] + B * arr[i - 1] + C) % D + 1;
}
int main() {
int T;
cin >> T;
for (int x = 1; x <= T; x++) {
int N, M, K, S;
cin >> N >> M >> K >> S;
vector<int> P(N), Q(M);
read_sequence(K, P);
read_sequence(K, Q);
cout << "Case #" << x << ": " << dislodging_logs(N, M, P, Q) << endl;
}
return 0;
}