Submission #336750

#	Time	Username	Problem	Language	Result	Execution time	Memory
336750		KWang31	Longest beautiful sequence (IZhO17_subsequence)	Java	23 / 100	6093 ms	177032 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());
    }
 
 
}
 

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