Submission #460753

#	Time	Username	Problem	Language	Result	Execution time	Memory
460753		grt	Cipele (COCI18_cipele)	C++17	90 / 90	50 ms	2892 KiB

cipele

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 100 * 1000 + 10, INF = 1e9 + 10;
int n, m;
vi a, b;

bool check(int x) {
	int ptr = 0;
	for(int i = 0; i < n; ++i) {
		while(ptr < m && a[i] - b[ptr] > x) {
			ptr++;
		}
		if(ptr < m && abs(a[i] - b[ptr]) <= x) {
			ptr++;
		} else {
			return false;
		}
	}
	return true;
}

int main() {_
	cin >> n >> m;
	a.resize(n); b.resize(m);
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < m; ++i) cin >> b[i];
	if(n > m) {
		swap(n, m);
		a.swap(b);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int low = 0, high = INF, mid;
	while(low <= high) {
		mid = (low + high) / 2;
		if(check(mid)) high = mid - 1;
		else low = mid + 1;
	}
	cout << high + 1;
	
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9