Submission #330565

#	Time	Username	Problem	Language	Result	Execution time	Memory
330565		KWang31	Longest beautiful sequence (IZhO17_subsequence)	Java	23 / 100	519 ms	17288 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]; Arrays.fill(map, -1);
         	int[] child=new int[N]; Arrays.fill(child,-1);
         	int mx;
         	for(int i=0;i<N;i++) {
         		mx=1;
         		for(int j=0;j<MAX;j++) {
         			if(Integer.bitCount(a[i]&j)!=k[i])continue;
         			
         			if(dp[j]+1>mx) {
         				//System.out.println(i+" "+a[i]+" "+j);
         				
         				mx=dp[j]+1; child[i]=map[j];//I may need to update child and map
         				
         			}
         		}
         		dp[a[i]]=mx; map[a[i]]=i;
         	}
         	int ind=0; int max=0;
         	for(int i=0;i<MAX;i++) {
         		if(dp[i]>max) {
         			max=dp[i]; ind=map[i];
         		}
         	}
         	//System.out.println(Arrays.toString(dp));
         	//System.out.println(Arrays.toString(child));
         	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