Submission #1178999


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>

using namespace std;

int main() {
	int n, m, K;
	cin >> n >> m >> K;

	vector<int> A(n), B(m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d", &B[i]);
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());

	int ok = (int)1e9 + 10;
	int ng = -1;
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		int cnt = 0;
		multiset<int> st(B.begin(), B.end());
		for (int i = 0; i < n; i++) {
			// A[i]-mid, A[i]+mid	
			auto it = st.lower_bound(A[i] - mid);
			if (it == st.end()) {
				continue;
			}
			if (*it > A[i] + mid) {
				continue;
			}
			cnt++;
			st.erase(it);
		}
		if (cnt >= K) {
			ok = mid;
		} else {
			ng = mid;
		}
	}
	cout << ok << endl;
}

Submission Info

Submission Time
Task B - チーム決め
User pekempey
Language C++14 (GCC 5.4.1)
Score 600
Code Size 929 Byte
Status
Exec Time 788 ms
Memory 5760 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:19:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
                     ^
./Main.cpp:22:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &B[i]);
                     ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt
All 600 / 600 in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
in1.txt 361 ms 5760 KB
in10.txt 362 ms 5760 KB
in11.txt 313 ms 5376 KB
in12.txt 302 ms 5248 KB
in13.txt 297 ms 5760 KB
in14.txt 321 ms 5760 KB
in15.txt 284 ms 5632 KB
in16.txt 278 ms 5760 KB
in17.txt 282 ms 5760 KB
in18.txt 280 ms 5760 KB
in19.txt 254 ms 5376 KB
in2.txt 360 ms 5760 KB
in20.txt 788 ms 5760 KB
in21.txt 285 ms 5760 KB
in22.txt 470 ms 5760 KB
in23.txt 262 ms 5760 KB
in3.txt 322 ms 5248 KB
in4.txt 369 ms 5760 KB
in5.txt 365 ms 5760 KB
in6.txt 278 ms 5632 KB
in7.txt 247 ms 5760 KB
in8.txt 254 ms 5760 KB
in9.txt 321 ms 5760 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB