Submission #1773587
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=70; boolean[][][] dp=new boolean[2][A][2*B]; 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); dp[0][0][B]=true; 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){ dp[0][i+1][j+1]|=dp[0][i][j];//0 m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[0][i][j]); } if(j>0){ dp[1][i+1][j-1]|=dp[0][i][j];//1 m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[0][i][j]|1L<<i); } dp[1][i+1][j]|=dp[1][i][j];//0,1 m[1][i+1][j]=Math.min(m[1][i+1][j],m[1][i][j]); } else { dp[0][i+1][j]|=dp[0][i][j];//0,1 m[0][i+1][j]=Math.min(m[0][i+1][j],m[0][i][j]); if(j<2*B-1){ dp[0][i+1][j+1]|=dp[1][i][j];//0 m[0][i+1][j+1]=Math.min(m[0][i+1][j+1],m[1][i][j]); } if(j>0){ dp[1][i+1][j-1]|=dp[1][i][j]; m[1][i+1][j-1]=Math.min(m[1][i+1][j-1],m[1][i][j]|1L<<i); } } } } //System.err.println("dp[0][A-1][B]=" + dp[0][A-1][B]); //System.err.println("m[0][A-1][B]=" + m[0][A-1][B]); 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
Submission Time | |
---|---|
Task | H - Bit Count |
User | kirika_comp |
Language | Java8 (OpenJDK 1.8.0) |
Score | 300 |
Code Size | 1995 Byte |
Status | AC |
Exec Time | 239 ms |
Memory | 42584 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 300 / 300 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample.txt | AC | 115 ms | 21076 KB |
10_small_00.txt | AC | 214 ms | 42332 KB |
20_medium_01.txt | AC | 219 ms | 38716 KB |
20_medium_02.txt | AC | 237 ms | 41304 KB |
20_medium_03.txt | AC | 201 ms | 38704 KB |
30_large_04.txt | AC | 239 ms | 41360 KB |
30_large_05.txt | AC | 237 ms | 42584 KB |
30_large_06.txt | AC | 227 ms | 41124 KB |
80_power_of_2.txt | AC | 115 ms | 21716 KB |