제출 #336599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336599		KWang31	Longest beautiful sequence (IZhO17_subsequence)	Java	23 / 100	6070 ms	177064 KiB

subsequence

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]; for(int i=0;i<MAX;i++)for(int j=0;j<MAX;j++)Arrays.fill(M[i][j],-1);
        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]; 
        Arrays.fill(prev, -1);
        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=0;i<N;i++) {
        	q=a[i]>>>10; r=a[i]&(MAX-1); 
                    ans[i]++;
        	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&q]]<ans[i]) {
                            M[j][r][btcnt[j&q]]=ans[i]; ind[j][r][btcnt[j&q]]=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(Arrays.toString(ans));
        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!

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60