Submission #330550

#	Time	Username	Problem	Language	Result	Execution time	Memory
330550		KWang31	Longest beautiful sequence (IZhO17_subsequence)	Java	23 / 100	456 ms	17380 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<<8;

    public static void main(String[] args){

        FastReader br=new FastReader();

        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();
        if(N<5000) {
        	int[] dp=new int[N]; Arrays.fill(dp, 1);
        	int[] child=new int[N];//Tracks the previous term of the sequence
        	Arrays.fill(child,-1);
        	for(int i=1;i<N;i++) {
        		for(int j=0;j<i;j++) {
        			if(Integer.bitCount(a[i]&a[j])==k[i]) {
        				if(1+dp[j]>dp[i]) {
        					dp[i]=dp[j]+1; child[i]=j;
        				}
        			}
        		}
        	}
        	
        	int max=0; int ind=-1;
        	for(int i=0;i<N;i++) {
        		if(dp[i]>max) {
        			max=dp[i]; ind=i;
        		}
        	}
        	
        	ArrayList<Integer> arl=new ArrayList<>();
        	while(ind >= 0) {
        		arl.add(ind);
        		
        		ind=child[ind];
        	}
        	System.out.println(max);
        	StringBuilder sb=new StringBuilder();
        	for(int i=arl.size()-1; i>=0; i--) {
        		sb.append(arl.get(i)+1).append(" ");
        	}
        	System.out.println(sb.toString());
        }else {
        	int[] dp=new int[MAX];
        	int[] map=new int[MAX];
        	int[] child=new int[N]; Arrays.fill(child,-1);
        	for(int i=0;i<N;i++) {
        		map[a[i]]=i;
        		for(int j=0;j<MAX;j++) {
        			if(Integer.bitCount(a[i]&j)!=k[i])continue;
        			if(dp[j]+1>dp[a[i]]) {
        				dp[a[i]]=dp[j]+1; child[i]=map[j];
        			}
        		}
        	}
        	int ind=0; int max=0;
        	for(int i=0;i<MAX;i++) {
        		if(dp[i]>max) {
        			max=dp[i]; ind=map[i];
        		}
        	}
        	ArrayList<Integer> arl=new ArrayList<>();
        	while(ind >= 0) {
        		arl.add(ind);
        		
        		ind=child[ind];
        	}
        	System.out.println(max);
        	StringBuilder sb=new StringBuilder();
        	for(int i=arl.size()-1; i>=0; i--) {
        		sb.append(arl.get(i)+1).append(" ");
        	}
        	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