京都大学プログラミングコンテスト2015

Submission #1773627

Source codeソースコード

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)
                for(int a=0;a<2;++a)
                    for(int k=0;k<2;++k){
                        int s=a+d+k;
                        int nj=j+(s&1)-a;
                        if(nj>=0&&nj<2*B)
                            m[s>>1][i+1][nj]=Math.min(m[s>>1][i+1][nj],m[k][i][j]|(long)a<<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

Task問題 H - Bit Count
User nameユーザ名 kirika_comp
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 300
Source lengthソースコード長 1011 Byte
File nameファイル名
Exec time実行時間 174 ms
Memory usageメモリ使用量 36596 KB

Test case

Set

Set name Score得点 / Max score Cases
All 300 / 300 00_sample.txt,10_small_00.txt,20_medium_01.txt,20_medium_02.txt,20_medium_03.txt,30_large_04.txt,30_large_05.txt,30_large_06.txt,80_power_of_2.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample.txt AC 104 ms 20948 KB
10_small_00.txt AC 161 ms 32980 KB
20_medium_01.txt AC 148 ms 32244 KB
20_medium_02.txt AC 150 ms 33788 KB
20_medium_03.txt AC 145 ms 32388 KB
30_large_04.txt AC 174 ms 34684 KB
30_large_05.txt AC 146 ms 35092 KB
30_large_06.txt AC 155 ms 36596 KB
80_power_of_2.txt AC 116 ms 22612 KB