oj.uz

Submission #394730

# Submission time Handle Problem Language Result Execution time Memory
394730 2021-04-27T08:39:13 Z Carmel_Ab1 Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 95008 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define gcd __gcd
#define popcount __builtin_popcountll
#define mp make_pair

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}
ll ceil(ll a,ll b){
    ll ans=a/b;
    if(a%b)ans++;
    return ans;
}
ld log (ld a,ld b){return log(b)/log(a);}
ll power(ll base, ll exp,ll M=1e9+7){//(base^exp)%M
    ll ans=1;
    while(exp){
        if(exp%2==1)ans=((ans%M)*(base%M))%M;
        base=((base%M)*(base%M))%M;
        exp/=2;
    }
    return ans;
}

string to_base(int n,int new_base){
    string s;
    int nn=n;
    while(nn){
        s+=to_string(nn%new_base);
        nn/=new_base;
    }
    reverse(all(s));
    return s;
}

ll lcm(ll a,ll b){
    ll x= (a/gcd(a,b));
    return b*x;
}
vl generate_array(ll n,ll mn=1,ll mx=1e18+1){
    if(mx==1e18+1)
        mx=n;
    vl ans(n);
    for(int i=0; i<n;i++)
        ans[i]=(mn+rand()%(mx-mn+1));
    return ans;
}
string substr(string s,int l,int r){
    string ans;
    for(int i=l; i<=r; i++)
        ans+=s[i];
    return ans;
}


void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
vector<string>a;
string s;
map<int,map<int,map<int,bool>>>can;
map<int,map<int,map<int,bool>>>vis;

bool dfs(int i,int j,int k){
    int n=a.size(),m=a[0].size();
    if(i<0 || j<0 || n<=i || m<=j || a[i][j]!='.')return 0;
    else if(k==s.size())return 1;
    if(vis[i][j][k])return can[i][j][k];
    vis[i][j][k]=1;

    if(s[k]=='?')return can[i][j][k]=dfs(i+1,j,k+1) || dfs(i,j+1,k+1) || dfs(i-1,j,k+1) || dfs(i,j-1,k+1);
    else if(s[k]=='W')return can[i][j][k]=dfs(i,j+1,k+1);
    else if(s[k]=='S')return can[i][j][k]=dfs(i-1,j,k+1);
    else if(s[k]=='N')return can[i][j][k]=dfs(i+1,j,k+1);
    else return can[i][j][k]=dfs(i,j-1,k+1);
}
void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    a.resize(n);

    read(a);
    cin >> s;
    reverse(all(s));
    int ans=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(a[i][j]=='.')
                dfs(i,j,0);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(can[i][j][0] && a[i][j]=='.'){
                ans++;
                //cout << i << " " << j << "\n";
            }
    out(ans)

}
/*
 5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
 */

Compilation message

nautilus.cpp: In function 'bool dfs(int, int, int)':
nautilus.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     else if(k==s.size())return 1;
      |             ~^~~~~~~~~~
nautilus.cpp: In function 'void usaco(std::string)':
nautilus.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
nautilus.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 85976 KB Output is correct
2 Correct 54 ms 10640 KB Output is correct
3 Correct 21 ms 5212 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 4 ms 1740 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 85976 KB Output is correct
2 Correct 54 ms 10640 KB Output is correct
3 Correct 21 ms 5212 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 4 ms 1740 KB Output is correct
7 Correct 761 ms 73620 KB Output is correct
8 Correct 54 ms 9156 KB Output is correct
9 Correct 12 ms 3380 KB Output is correct
10 Correct 5 ms 2252 KB Output is correct
11 Correct 3 ms 1740 KB Output is correct
12 Correct 831 ms 59172 KB Output is correct
13 Correct 95 ms 14168 KB Output is correct
14 Correct 68 ms 11188 KB Output is correct
15 Correct 12 ms 3268 KB Output is correct
16 Correct 3 ms 1740 KB Output is correct
17 Correct 306 ms 49652 KB Output is correct
18 Correct 73 ms 14888 KB Output is correct
19 Correct 76 ms 16668 KB Output is correct
20 Correct 53 ms 9668 KB Output is correct
21 Correct 3 ms 1868 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 85976 KB Output is correct
2 Correct 54 ms 10640 KB Output is correct
3 Correct 21 ms 5212 KB Output is correct
4 Correct 7 ms 2636 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 4 ms 1740 KB Output is correct
7 Correct 761 ms 73620 KB Output is correct
8 Correct 54 ms 9156 KB Output is correct
9 Correct 12 ms 3380 KB Output is correct
10 Correct 5 ms 2252 KB Output is correct
11 Correct 3 ms 1740 KB Output is correct
12 Correct 831 ms 59172 KB Output is correct
13 Correct 95 ms 14168 KB Output is correct
14 Correct 68 ms 11188 KB Output is correct
15 Correct 12 ms 3268 KB Output is correct
16 Correct 3 ms 1740 KB Output is correct
17 Correct 306 ms 49652 KB Output is correct
18 Correct 73 ms 14888 KB Output is correct
19 Correct 76 ms 16668 KB Output is correct
20 Correct 53 ms 9668 KB Output is correct
21 Correct 3 ms 1868 KB Output is correct
22 Execution timed out 1075 ms 95008 KB Time limit exceeded
23 Halted 0 ms 0 KB -