Submission #158350

#	Time	Username	Problem	Language	Result	Execution time	Memory
158350		cn355	Cipele (COCI18_cipele)	Java	45 / 90	395 ms	17748 KiB

cipele

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++;
			}
		}
		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(); 
        } 
    } 
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 9 / 9
• Subtask 10: 0 / 9