Submission #489547

#TimeUsernameProblemLanguageResultExecution timeMemory
489547kiomiNautilus (BOI19_nautilus)C++17
100 / 100
147 ms720 KiB
//#pragma GCC target ("avx2") //#pragma GCC optimization ("Ofast") //#pragma GCC optimization ("unroll-loops") //#pragma comment(linker,"/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //order_of_key(k): Number of items strictly smaller than k . //find_by_order(k): K-th element in a set (counting from zero). #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define full(x,n) x,x+n+1 #define full(x) x.begin(),x.end() #define finish return 0 #define putb push_back #define f first #define s second //logx(a^n)=loga(a^n)/logx(a) //logx(a*b)=logx(a)+logx(b) //logx(y)=log(y)/log(x) //logb(n)=loga(n)/loga(b) #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define putf push_front #define gainb pop_back //(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n //(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i #define gainf pop_front #define len(x) (int)x.size() // 1/b%mod=b^(m-2)%mod // (a>>x)&1==0 // a^b=(a+b)-2(a&b) typedef double db; typedef long long ll; //sum of squares n*(n+1)*(2n+1)/6 //sum of cubes [n*(n+1)/2]^2 //sum of squares for odds n*(4*n*n-1)/3 //sum of cubes for odds n*n*(2*n*n-1) const int ary=500; const ll mod=1e9+7; const ll inf=1e18; using namespace std; using namespace __gnu_pbds; bitset<ary> d[3][ary]; int r,c,m,ans; char a; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>r>>c>>m; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ cin>>a; d[1][i][j]=(a=='.'); d[2][i][j]=d[1][i][j]; } } cin>>s; for(int i=0;i<m;i++){ int x=i%2; int y=1-x; for(int j=0;j<r;j++){ if(s[i]=='?'||s[i]=='N'){ if(j+1<r){ d[x][j]|=d[y][j+1]; } } if(s[i]=='?'||s[i]=='S'){ if(j-1>=0){ d[x][j]|=d[y][j-1]; } } if(s[i]=='?'||s[i]=='W'){ d[x][j]|=(d[y][j]>>1); } if(s[i]=='?'||s[i]=='E'){ d[x][j]|=(d[y][j]<<1); } } for(int j=0;j<r;j++){ d[x][j]&=d[2][j]; if(i==m-1){ ans+=d[x][j].count(); } d[y][j].reset(); } } cout<<ans; }

Compilation message (stderr)

nautilus.cpp:15: warning: "full" redefined
   15 | #define full(x) x.begin(),x.end()
      | 
nautilus.cpp:14: note: this is the location of the previous definition
   14 | #define full(x,n) x,x+n+1
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...