| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158351 |
2019-10-16T16:14:28 Z |
cn355 |
Cipele (COCI18_cipele) |
Java 11 |
|
373 ms |
17160 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;
}
};
static final long LARGE_LONG = 1000000000000000000L;
static final int LARGE_INT = 1000000007;
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)) {
high = middle;
} else {
low = middle + 1;
}
}
out.println(low);
out.close();
}
static boolean check(int[] a, int[] b, int gap) {
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;
if (aa < b[j] - gap) return false; // a[i] too small
if (aa > b[j] + gap) {
while (j <= ibound && aa > b[j] + gap) j++;
if (j > ibound) return false; // a[i] too large
else j++;
} else {
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 |
187 ms |
11300 KB |
Output is correct |
| 2 |
Correct |
368 ms |
15180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
271 ms |
12680 KB |
Output is correct |
| 2 |
Correct |
322 ms |
15760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
9840 KB |
Output is correct |
| 2 |
Correct |
127 ms |
10760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
10772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
10808 KB |
Output is correct |
| 2 |
Correct |
137 ms |
10884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
10828 KB |
Output is correct |
| 2 |
Correct |
125 ms |
11240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
130 ms |
11460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
15428 KB |
Output is correct |
| 2 |
Correct |
316 ms |
15432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
15352 KB |
Output is correct |
| 2 |
Correct |
180 ms |
11692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
16180 KB |
Output is correct |
| 2 |
Correct |
347 ms |
17160 KB |
Output is correct |
