| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158355 |
2019-10-16T16:34:36 Z |
cn355 |
Cipele (COCI18_cipele) |
Java 11 |
|
381 ms |
15900 KB |
import java.io.*;
import java.util.*;
public class cipele {
static String probName = "cipele";
static Comparator<int[]> comp = new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
for (int i=0; i<a.length; i++) {
if (a[i] < b[i]) return -1;
else if (a[i] > b[i]) return 1;
}
return 0;
}
};
public static void main(String[] args) throws IOException {
FastReader in = new FastReader();
PrintWriter out = new PrintWriter(System.out);
int N = in.nextInt(), M = in.nextInt();
int[] left = new int[N], right = new int[M];
for (int i = 0; i < N; i++) {
left[i] = in.nextInt();
}
for (int i = 0; i < M; i++) {
right[i] = in.nextInt();
}
Arrays.sort(left);
Arrays.sort(right);
int low = 0, high = 1000000000;
while (low < high) {
int middle = low + (high-low) / 2;
if (check(left, right, middle, out)) {
high = middle;
} else {
low = middle + 1;
}
}
out.println(low);
out.close();
}
static boolean check(int[] a, int[] b, int gap, PrintWriter out) {
if (a.length > b.length) {
int[] c = b;
b = a;
a = c;
}
int m = a.length, extra = b.length - m, j = 0;
for (int i=0; i<m; i++) {
int aa = a[i], ibound = i + extra;
while (j <= ibound && (aa < b[j] - gap || aa > b[j] + gap)) j++;
if (j > ibound) return false; // a[i] too large
j++;
}
return true;
}
/* FastReader code from https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ */
static class FastReader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public FastReader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public FastReader(String file_name) throws IOException {
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg) c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg) return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null) return;
din.close();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
11660 KB |
Output is correct |
| 2 |
Correct |
381 ms |
15900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
12564 KB |
Output is correct |
| 2 |
Correct |
278 ms |
14972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
9772 KB |
Output is correct |
| 2 |
Correct |
127 ms |
11264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
10888 KB |
Output is correct |
| 2 |
Correct |
145 ms |
11772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
10724 KB |
Output is correct |
| 2 |
Correct |
123 ms |
10784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
10676 KB |
Output is correct |
| 2 |
Correct |
125 ms |
10944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
10768 KB |
Output is correct |
| 2 |
Correct |
124 ms |
10668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
12748 KB |
Output is correct |
| 2 |
Correct |
219 ms |
12156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
15676 KB |
Output is correct |
| 2 |
Correct |
172 ms |
11676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
353 ms |
15900 KB |
Output is correct |
| 2 |
Correct |
341 ms |
15088 KB |
Output is correct |
