Submission #146376

#	Time	Username	Problem	Language	Result	Execution time	Memory
146376		badrovinho	Cipele (COCI18_cipele)	C++11	63 / 90	162 ms	3056 KiB

cipele

#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 / 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: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9