oj.uz

Submission #460753

# Submission time Handle Problem Language Result Execution time Memory
460753 2021-08-09T09:09:37 Z grt Cipele (COCI18_cipele) C++17
90 / 90
 50 ms 2892 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2628 KB Output is correct
2 Correct 46 ms 2880 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2892 KB Output is correct
2 Correct 47 ms 2888 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 9 ms 332 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2360 KB Output is correct
2 Correct 32 ms 1792 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2628 KB Output is correct
2 Correct 22 ms 2040 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2356 KB Output is correct
2 Correct 40 ms 2508 KB Output is correct