Submission #336568

#	Time	Username	Problem	Language	Result	Execution time	Memory
336568		KWang31	Longest beautiful sequence (IZhO17_subsequence)	Java	0 / 100	538 ms	174824 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];
        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=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!

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