oj.uz

Submission #146376

# Submission time Handle Problem Language Result Execution time Memory
146376 2019-08-23T15:57:13 Z badrovinho Cipele (COCI18_cipele) C++11
63 / 90
 162 ms 3056 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

	int l[100005];
	int r[100005];

int main (){
	
	int n,m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++){
		cin >> l[i];
	}
	
	for (int i = 0; i < m; i++){
		cin >> r[i];
	}
	
	sort(l, l + n);
	sort(r, r + m);
	
	int lo = 0;
	int hi = 1000000000;
	int mid = hi / 2;
	
	while (lo != hi){
		
		if (n >= m){
			int raz = n - m;
			int ptl = 0;
			int ptr = 0;
			int sol = 0;
			for (int i = 0; i < m; i++){
				for (int j = 0; j < raz + 1; j++){
					if ((abs (l[ptl]-r[ptr])) <= mid){
						ptr++;
						ptl++;
						break;
					}
					if ((abs (l[ptl]-r[ptr])) > mid){
						sol++;
					}
					ptl++;
				}
			}
			if (sol > raz){
				lo = mid+1;
				mid = (hi+lo)/2;
			}else {
				hi = mid;
				mid = (hi+lo)/2;
			}
		}{
		
			int raz = m - n;
			int ptl = 0;
			int ptr = 0;
			int sol = 0;
			for (int i = 0; i < n; i++){
				for (int j = 0; j < raz + 1; j++){
					if ((abs (r[ptr]-l[ptl])) <= mid){
						ptr++;
						ptl++;
						break;
					}
					if ((abs (r[ptr]-l[ptl])) > mid){
						sol++;
					}
					ptr++;
				}
			}
			if (sol > raz){
				lo = mid+1;
				mid = (hi+lo)/2;
			}else {
				hi = mid;
				mid = (hi+lo)/2;
			}
		
		}
		
	}
	
	cout << mid;
	
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2680 KB Output is correct
2 Correct 161 ms 2936 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 2876 KB Output is correct
2 Correct 161 ms 3056 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 12 ms 504 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 520 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 11 ms 504 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 11 ms 504 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 11 ms 504 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2452 KB Output is correct
2 Incorrect 91 ms 1912 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2616 KB Output is correct
2 Incorrect 97 ms 2040 KB Output isn't correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2448 KB Output is correct
2 Incorrect 137 ms 2544 KB Output isn't correct