제출 #336567

#제출 시각아이디문제언어결과실행 시간메모리
336567KWang31Longest beautiful sequence (IZhO17_subsequence)Java
0 / 100
534 ms174804 KiB
import java.io.*; import java.util.*; public class subsequence{ static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } } static int MOD=998244353; static int MAX=1<<10; public static void main(String[] args){ FastReader br=new FastReader(); int[] btcnt=new int[MAX]; for(int i=0;i<MAX;i++) {btcnt[i]=Integer.bitCount(i);} int[][][] M=new int[MAX][MAX][11]; int[][][] ind=new int[MAX][MAX][11]; int N=br.nextInt(); int[] a=new int[N]; int[] k=new int[N]; for(int i=0;i<N;i++) {a[i]=br.nextInt();} for(int i=0;i<N;i++) {k[i]=br.nextInt();} int q=0; int r=a[0]&(MAX-1); int z; int[] prev=new int[N]; int[] ans=new int[N]; ans[0]=1; for(int j=0;j<MAX;j++) { M[j][r][btcnt[j&r]]++; ind[j][r][btcnt[j&r]]=0; } for(int i=1;i<N;i++) { q=a[i]>>>10; r=a[i]&(MAX-1); for(int j=0;j<MAX;j++) {//QUERY z=k[i]-btcnt[r&j]; if(z>=0 && z<=10) { //The first 10 bits have EXACTLY z bits in common if( M[q][j][z]+1>ans[i]) { ans[i]=M[q][j][z]+1; prev[i]=ind[q][j][z]; } } } //UPDATE for(int j=0;j<MAX;j++) { if(M[j][r][btcnt[j&r]]<ans[i]) { M[j][r][btcnt[j&r]]=ans[i]; ind[j][r][btcnt[j&r]]=i; } } } int mx=0; int cur=-1; for(int i=0;i<N;i++) { if(ans[i]>mx) { mx=ans[i]; cur=i; } } System.out.println(mx); ArrayList<Integer> arl=new ArrayList<>(); arl.add(cur+1); while(cur>0) { cur=prev[cur]; arl.add(cur+1); } StringBuilder sb=new StringBuilder(); for(int i=mx-1;i>=0;i--) { sb.append(arl.get(i)+" "); } System.out.println(sb.toString()); } } //Debugging: //Are you sure your algorithm is correct? //Bounds: long //Special cases: n=0,1? //Make sure you remove your debugging code before you submit!
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...