Submission #329024

#TimeUsernameProblemLanguageResultExecution timeMemory
329024KWang31Nautilus (BOI19_nautilus)Java
0 / 100
131 ms10656 KiB
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 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 long[] ans; for (int i = 0; i < M; i++) { if(s.charAt(i)=='E'){//Shift right for (int j = 0; j < R; j++) { ans=new long[(C+63)/64]; dp[j]=shift(dp[j],1,j,ans); } }else if(s.charAt(i)=='W'){ for (int j = 0; j < R; j++) { ans=new long[(C+63)/64]; dp[j]=shift(dp[j],-1,j,ans); } }else if(s.charAt(i)=='N'){ //System.out.println("map[1][0] "+map[1][0]); 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]; } } //System.out.println("map[1][0]..."+map[1][0]); for (int j = 0; j < (C+63)/64; j++) { dp[R-1][j]=0; //System.out.println("map[1][0]::: "+map[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]; long[] b=new long[(C+63)/64]; for (int j = 0; j <R; j++) { a[j]=shift(dp[j],1,j,a[j]); b=shift(dp[j],-1,j,b); for (int k = 0; k <(C+63)/64; k++) { a[j][k]|=b[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++) { System.out.println(dp[i][j]); res+=Long.bitCount(dp[i][j]); } } System.out.println(res); } public static long[] shift(long[] a, int c, int ind, long[] ans){ int len=(63+C)/64; 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 for (int i = 1; i < len; i++) { long b=a[i]&1; ans[i-1]|=((long)b<<63); ans[i]|=a[i]>>>1; } ans[0]|=a[0]>>>1; } for (int i = 0; i <(C+63)/64; i++) { ans[i]&=map[ind][i]; } return ans; } } //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!
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...