Submission #707078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707078	2023-03-08T11:42:40 Z	TAhmed33	Cipele (COCI18_cipele)	C++	90 / 90	127 ms	3648 KB

cipele

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int arr[100001] = {};
int arr2[100001] = {};
bool check (int x) {
	int pos = 1;
	for (int i = 1; i <= n; i++) {
		int q = lower_bound(arr2 + pos, arr2 + m + 1, arr[i] - x) - arr2;
		if (q == m + 1) return false;

		if (abs(arr2[q] - arr[i]) > x) return false;
		pos = q + 1;
	}
	return true;
}
signed main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int j = 1; j <= m; j++) {
		cin >> arr2[j];
	}
	sort(arr + 1, arr + n + 1);
	sort(arr2 + 1, arr2 + m + 1);
	if (n > m) {
		swap(n, m);
		for (int i = 1; i <= 100000; i++) swap(arr[i], arr2[i]);
	}
	int l = 0, r = 1e9;
	int mid, ans = 2;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << '\n';
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	3372 KB	Output is correct
2	Correct	121 ms	3648 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	122 ms	3644 KB	Output is correct
2	Correct	127 ms	3532 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	280 KB	Output is correct
2	Correct	6 ms	484 KB	Output is correct

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	6 ms	488 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	380 KB	Output is correct
2	Correct	6 ms	424 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	340 KB	Output is correct
2	Correct	8 ms	448 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	3016 KB	Output is correct
2	Correct	76 ms	2876 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	3280 KB	Output is correct
2	Correct	71 ms	2936 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	2892 KB	Output is correct
2	Correct	100 ms	3356 KB	Output is correct