Submission #337234

#	Time	Username	Problem	Language	Result	Execution time	Memory
337234		KWang31	Snake Escaping (JOI18_snake_escaping)	Java	100 / 100	1752 ms	65536 KiB

snake_escaping

import java.io.*; import java.util.*;
public class snake_escaping{
  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()); 
        } 
  
        
    } 
  
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=998244353;
    
    public static void main(String[] args){
        FastReader br=new FastReader();
        int L=br.nextInt(); int Q=br.nextInt();
        final int[] S=new int[1<<L]; final int[] sup=new int[1<<L]; final int[] sub=new int[1<<L];
        final int[] btcnt=new int[1<<L];
        String s=br.next();
        for(int i=0; i<(1<<L); i++){
            S[i]=(int) s.charAt(i)-'0'; sup[i]=sub[i]=S[i];
            btcnt[i]=Integer.bitCount(i);
        }
        //SOS DP!!
        for(int b=0; b<L; b++){
            for(int m=0;m<(1<<L); m++){
                if(((m>>>b)&1) ==0){
                    sup[m]+=sup[m^(1<<b)];
                }else{
                    sub[m]+=sub[m^(1<<b)];
                }
            }
        }
        //System.out.println(Arrays.toString(sub));
        //System.out.println(Arrays.toString(sup));
        StringBuilder sb=new StringBuilder();
        //sb can have a lot of memory
        int A; int B; int C;
        int ca; int cb; int cc; long ans;
        for(int i=0;i<Q;i++){
            s=br.next(); A=0; B=0; C=0;
            ca=0; cb=0; cc=0; ans=0;
            for(int j=0;j<L;j++){
                if(s.charAt(j)=='0'){A|=(1<<(L-j-1)); ca++;}
                else if(s.charAt(j)=='1') {B|=(1<<(L-j-1)); cb++;}
                else {C|=(1<<(L-j-1)); cc++;}
            }
            //System.out.println(ca+" "+cb+" "+cc);
            if(ca<=cb && ca<=cc){
                for(int m=A; m!=0; m=(m-1)&A){
                    ans+=(1-2*((btcnt[m])&1))*sup[B|m];
                }
                ans+=sup[B];
            }else if(cb<=ca && cb<=cc){
                for(int m=B; m!=0; m=(m-1)&B){
                    
                    ans+=(1-2*((btcnt[m])&1))*sub[C|(B^m)];
                    
                }
                ans+=sub[C|B];
                
            }else{
                for(int m=C; m!=0; m=(m-1)&C){
                    
                    ans+=S[m|B];
                }
                //System.out.println(A+" "+B);
                ans+=S[B];
            }
            sb.append(ans).append("\n");
            if((i&((1<<17)-1))==0){
                System.out.println(sb.toString());
                sb=new StringBuilder();
            }
        }
        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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25