oj.uz

Submission #146386

# Submission time Handle Problem Language Result Execution time Memory
146386 2019-08-23T16:17:05 Z badrovinho Cipele (COCI18_cipele) C++11
27 / 90
 167 ms 3564 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++;
					}
					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;
			}
		} else {
		
			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++;
					}
					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 << "srednji mid je --> " << mid << endl;	
	}
	
	cout << mid;
	
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 2584 KB Output is correct
2 Correct 165 ms 2920 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2904 KB Output is correct
2 Correct 164 ms 2908 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 128 ms 3180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 3564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -