Submission #63890980

---

Source Code Expand

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
    static int N,L;
    static int[] T;
    static int div = 16;
    static int[] two = new int[div];
    static ArrayDeque<Integer>[] group;

    static Pair[] pairs;
    public static void main(String[] args) {
        init();

        setPairs();

        setGroups();

        setAB();
    }

    private static void init(){
        FastScanner sc = new FastScanner();

        N = sc.nextInt();
        L = sc.nextInt();

        T = new int[N];
        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();
        }
    }

    private static void setPairs(){
        pairs = new Pair[N];
        for (int i = 0; i < N; i++) {
            pairs[i] = new Pair(T[i],i);
        }

        Arrays.sort(pairs);

        // for (int i = 0; i < N; i++) {
        //     System.out.println(pairs[i].t);
        // }
    }

    private static void setGroups(){
        group = new ArrayDeque[div];
        for (int i = 0; i < div; i++) {
            group[i] = new ArrayDeque<>();
        }

        two[0] = 1;
        for (int i = 1; i < div; i++) {
            two[i] = two[i-1]*2;
        }

        group[0].add(0);
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < div; j++) {
                if (Math.abs(T[i] - two[j-1]) > Math.abs(T[i] - two[j]) && Math.abs(T[i] - two[j+1]) > Math.abs(T[i] - two[j])){
                    group[j].add(i);
                    break;
                }
            }
        }
    }

    private static void setAB(){
        int[] ret = new int[div];
        Arrays.fill(ret,-1);
        int[] ans = new int[N];
        int index = 0;
        // System.out.println("ret");
        for (int i = 0; i < div; i++) {
            if (group[i].isEmpty()) continue;

            ret[i] = group[i].remove();
            // System.out.println(ret[i]);
            ans[index] = ret[i];
            index++;
        }

        int[] a = new int[N];
        int[] b = new int[N];
        Arrays.fill(a,-1);
        Arrays.fill(b,-1);

        for (int i = div - 1; i >= 0; i--) {
            while (!group[i].isEmpty()){
                ans[index] = group[i].remove();
                index++;
            }
            if (ret[i] != -1) {
                a[index - 1] = i;
            }
        }

        // System.out.println(ans[1]);

        // for (int i = 0; i < N; i++) {
        //     System.out.println(ans[a[i]] + " " + ans[b[i]]);
        // }

        for (int i = 0; i < N-1; i++) {
            if (a[i] == -1){
                a[i] = i+1;
            }
            if (b[i] == -1){
                b[i] = i+1;
            }
        }
        a[N-1] = 0;
        b[N-1] = 0;

        // System.out.println("ans");
        // for (int i = 0; i < N; i++) {
        //     System.out.println(ans[i]);
        // }
//
        // System.out.println("ab");
        // for (int i = 0; i < N; i++) {
        //     System.out.println(a[i] + " " + b[i]);
        // }
//
        // System.out.println("out");
        // for (int i = 0; i < N; i++) {
        //     System.out.println(ans[a[i]] + " " + ans[b[i]]);
        // }

        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[ans[i]] = ans[a[i]];
            B[ans[i]] = ans[b[i]];
        }

        // System.out.println("true");
        System.out.println(ans[1] + " " + ans[1]);
        for (int i = 1; i < N; i++) {
            System.out.println(A[i] + " " + B[i]);
        }
    }

    private static class Pair implements Comparable<Pair>{
        int t, index;
        public Pair(int A,int B){
            t = A;
            index = B;
        }

        @Override
        public int compareTo(Pair o) {
            return Integer.compare(t,o.t);
        }
    }

    private static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return buflen > 0;
            }
        }

        private int readByte() {
            if (hasNextByte()) return buffer[ptr++];
            else return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return !hasNextByte();
        }

        public String next() {
            if (hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

Submission Info

Compile Error

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result