Submission #260308

#TimeUsernameProblemLanguageResultExecution timeMemory
260308arnold518Nautilus (BOI19_nautilus)C++14
66 / 100
1102 ms197592 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 500; const int MAXM = 5000; int R, C, M; char S[MAXN+10][MAXN+10]; char A[MAXM+10]; int B[MAXN+10][MAXN+10]; int adj[(1<<20)+10]; int D[MAXN+10][MAXN/20+10][MAXM+10]; int main() { scanf("%d%d%d", &R, &C, &M); for(int i=1; i<=R; i++) scanf("%s", S[i]+1); scanf("%s", A+1); for(int i=1; i<=R; i++) for(int j=1; j<=C; j++) if(S[i][j]=='.') B[i][j/20]|=(1<<(j%20)); for(int i=1; i<=R; i++) for(int j=0; j<=C/20; j++) D[i][j][0]=B[i][j]; for(int i=0; i<(1<<20); i++) { for(int j=0; j<20; j++) { int t=0; if(j!=0 && (i&(1<<(j-1)))) t=1; if(j!=19 && (i*(1<<(j+1)))) t=1; adj[i]|=(t<<j); } } for(int p=1; p<=M; p++) { if(A[p]=='N') { for(int i=1; i<R; i++) for(int j=0; j<=C/20; j++) { D[i][j][p]=D[i+1][j][p-1]; D[i][j][p]&=B[i][j]; } } if(A[p]=='S') { for(int i=2; i<=R; i++) for(int j=0; j<=C/20; j++) { D[i][j][p]=D[i-1][j][p-1]; D[i][j][p]&=B[i][j]; } } if(A[p]=='E') { for(int i=1; i<=R; i++) { for(int j=C/20; j>=0; j--) { D[i][j][p]=D[i][j][p-1]<<1; D[i][j][p]&=((1<<20)-1); if(j!=0 && (D[i][j-1][p-1]&(1<<19))) D[i][j][p]|=1; D[i][j][p]&=B[i][j]; } } } if(A[p]=='W') { for(int i=1; i<=R; i++) { for(int j=0; j<=C/20; j++) { D[i][j][p]=D[i][j][p-1]>>1; if(j!=C/20 && (D[i][j+1][p-1]&1)) D[i][j][p]|=(1<<19); D[i][j][p]&=B[i][j]; } } } if(A[p]=='?') { for(int i=1; i<R; i++) for(int j=0; j<=C/20; j++) { int t; t=D[i+1][j][p-1]; D[i][j][p]|=t; } for(int i=2; i<=R; i++) for(int j=0; j<=C/20; j++) { int t; t=D[i-1][j][p-1]; D[i][j][p]|=t; } for(int i=1; i<=R; i++) { for(int j=C/20; j>=0; j--) { int t; t=D[i][j][p-1]<<1; t&=((1<<20)-1); if(j!=0 && (D[i][j-1][p-1]&(1<<19))) t|=1; D[i][j][p]|=t; } } for(int i=1; i<=R; i++) { for(int j=0; j<=C/20; j++) { int t; t=D[i][j][p-1]>>1; if(j!=C/20 && (D[i][j+1][p-1]&1)) t|=(1<<19); t&=B[i][j]; D[i][j][p]|=t; } } for(int i=1; i<=R; i++) for(int j=0; j<=C/20; j++) D[i][j][p]&=B[i][j]; } } int ans=0; for(int i=1; i<=R; i++) for(int j=0; j<=C/20; j++) ans+=__builtin_popcount(D[i][j][M]); printf("%d\n", ans); }

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:33:18: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
    if(j!=19 && (i*(1<<(j+1)))) t=1;
                ~~^~~~~~~~~~~~
nautilus.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &R, &C, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=R; i++) scanf("%s", S[i]+1);
                          ~~~~~^~~~~~~~~~~~~~
nautilus.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A+1);
  ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...