| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 329009 | KWang31 | Nautilus (BOI19_nautilus) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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 i=0;i<R;i++){
for(int j=0;j<(C+63)/64; j++){
dp[i][j]=a[i][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 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
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];
}
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!