Submission #329069

#	Time	Username	Problem	Language	Result	Execution time	Memory
329069		KWang31	Nautilus (BOI19_nautilus)	Java	66 / 100	1000 ms	21888 KiB

nautilus

import java.io.*; import java.util.*;
public class nautilus{
  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 long[][] map;
    static long[][] dp;
    static long[] ans;
    static int R,C;
    public static void main(String[] args){
        /*
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 65; j++) {
                System.out.print(".");
            }
            System.out.println("");
        }*/
        
        FastReader br=new FastReader();
        R=br.nextInt(); C=br.nextInt();int M=br.nextInt();
        map=new long[R][(C+63)/64]; String s;
        for (int i = 0; i < R; i++) {//Setting up the map
            s=br.next();
            
            for (int j = 0; j < C; j+=64) {
                for (int k = 0; k <Math.min(C-j,64); k++) {
                    
                    if(j+k<C && s.charAt(j+k)=='.'){
                        
                        map[i][j/64]|=(long) 1<<k;
                        //System.out.println(i+"::"+j+"::"+map[i][j/64]);
                    }
                }
            }
        }
        
        s=br.next(); dp=new long[R][(C+63)/64];
        for(int i=0;i<R;i++){
            for(int j=0;j<(C+63)/64; j++){
                dp[i][j]=map[i][j];//All positions are reachable with 0 moves
            }
        }	
      
        
        for (int i = 0; i < M; i++) {
            if(s.charAt(i)=='E'){//Shift right
                for (int j = 0; j < R; j++) {
                    
                    shift(dp[j],1,j);
                    dp[j]=ans.clone();
                }
            }else if(s.charAt(i)=='W'){
                for (int j = 0; j < R; j++) {
                    
                    shift(dp[j],-1,j);
                    dp[j]=ans.clone();
                }
            }else if(s.charAt(i)=='N'){
                for (int j = 0; j < R-1; j++) {
                    for (int k = 0; k <(C+63)/64; k++) {
                        dp[j][k]=dp[1+j][k]&map[j][k];
                    }
                }
                Arrays.fill(dp[R-1],0);
                
            }else if(s.charAt(i)=='S'){
                for (int j = R-1; j > 0; j--) {
                   
                    
                    for (int k = 0; k <(C+63)/64; k++) {
                        dp[j][k]=dp[j-1][k]&map[j][k];
                    }
                }
                
                Arrays.fill(dp[0],0);
                
            }else{//Take the OR of all four, then AND the map
                long[][] a=new long[R][(C+63)/64];
                
                for (int j = 0; j <R; j++) {
                    
                    shift(dp[j],1,j);
                    a[j]=ans.clone();
                    
                    shift(dp[j],-1,j);
                    for (int k = 0; k < (C+63)/64;k++) {
                        a[j][k]|=ans[k];
                    }
                    if(j>0){
                        for (int k = 0; k <(C+63)/64; k++) {
                            a[j][k]|=dp[j-1][k];
                        }
                    }
                    if(j<R-1){
                        for (int k = 0; k <(C+63)/64; k++) {
                            a[j][k]|=dp[j+1][k];
                        }
                    }
                    //Do I need to make a[.][k] 0? No! They would not be affected because I have ORed them with the correct stuff.
                    for (int k = 0; k <(C+63)/64; k++) {
                        a[j][k]&=map[j][k];
                    }
                }
                for(int k=0;k<R;k++){
	for(int j=0;j<(C+63)/64; j++){
                            dp[k][j]=a[k][j];
	}
                }
            }
            
        }
        int res=0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j <(C+63)/64; j++) {
                
                res+=Long.bitCount(dp[i][j]);
            }
        }
        System.out.println(res);
    }
    public static void shift(long[] a, int c, int ind){
        int len=(63+C)/64; ans=new long[len];
        if(c==1){
            long x=(long) 1<<63;
            for (int i = 0; i < len-1; i++) {
                long b=a[i]&(x-1);
                ans[i]|=((long) b<<1);
                long d=a[i]>>>63;//3>'s, 2>'s don't work
                ans[i+1]|=d;
            }
            //Take care of last bit
            ans[len-1]|=(a[len-1]<<1);
        }else{//c=-1
            ans[0]=a[0]>>>1;
            for (int i = 1; i < len; i++) {
                long b=a[i]&1;
                ans[i-1]|=((long)b<<63);
                ans[i]|=a[i]>>>1;
            }
        }
        for (int i = 0; i <(C+63)/64; i++) {
            ans[i]&=map[ind][i];
        }
        
    }
}
//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: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34