Submission #1773594

---

Source Code Expand

import java.util.*;

class Main {
    static final long I=(1L<<62-1);
    static long f(long n){
        final int A=60;
        final int B=65;
        long[][][] m=new long[2][A][2*B];
        for(int i=0;i<2;++i)
            for(int j=0;j<A;++j)
                Arrays.fill(m[i][j],I);
        m[0][0][B]=0;
        for(int i=0;i<A-1;++i){
            int d=(n&1L<<i)!=0?1:0;
            for(int j=0;j<2*B;++j){
                if(d==1){
                    if(j<2*B-1)
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[0][i][j]);
                    if(j>0)
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[0][i][j]|1L<<i);
                    m[1][i+1][j]=Math.min(m[1][i+1][j],m[1][i][j]);
                }else{
                    m[0][i+1][j]=Math.min(m[0][i+1][j],m[0][i][j]);
                    if(j<2*B-1)
                        m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[1][i][j]);
                    if(j>0)
                        m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[1][i][j]|1L<<i);
                }
            }
        }
        return m[0][A-1][B];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t=scan.nextInt();
        while(t-->0)
            System.out.println(f(scan.nextLong()));
    }
}

Submission Info

Judge Result