oj.uz

Submission #550875

# Submission time Handle Problem Language Result Execution time Memory
550875 2022-04-19T10:57:54 Z Bobonbush Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 237432 KB 
#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if(x == -1 || x >y)
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */

int n , m , k;

char a[501][501];
string s;

struct TrangThai
{
    int i , j , kay;
    TrangThai()
    {

    }
    TrangThai(int _i , int _j , int _kay)
    {
        i = _i;
        j = _j;
        kay = _kay;
    }
};
map<char , pair<int ,int >>diction;
map<pair<pair<int ,int > , int > , bool>dict;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , -1 , 1};
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    diction['W'] = make_pair(0 , -1);
    diction['S'] = make_pair(1 , 0);
    diction['E'] = make_pair(0 , 1);
    diction['N'] = make_pair(-1 , 0);
    cin >> n >> m >> k;
    for(int i =1 ; i <= n ; i++ )
    {
        for(int j =1; j <= m ; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> s;
    queue<TrangThai>q;
    for(int i = 1; i <= n ; i ++)
    {
        for(int j = 1; j <= m ; j++)
        {
            if(a[i][j] =='.')
            {
                q.push(TrangThai(i , j , 0));
                dict[make_pair(make_pair(i , j) , 0 )] = true;
            }
        }
    }
    int res = 0;
    while(!q.empty())
    {
        TrangThai _trangthai = q.front();
        q.pop();
        int i = _trangthai.i;
        int j = _trangthai.j;
        int kay = _trangthai.kay;
        if(kay == (int)s.size() + 1)
        {
            res++;
            continue;
        }
        if(s[kay] != '?')
        {
            int x = i + diction[s[kay]].first;
            int y = j + diction[s[kay]].second;
            if(x < 1 || x > n ||  y < 1 || y > m)
            {
                continue;
            }
            if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
            {
                continue;
            }
            dict[make_pair( make_pair(x , y), kay + 1)] = true;
            q.push(TrangThai(x , y , kay + 1));
            continue;
        }

        for(int z = 0 ; z < 4 ; z++)
        {
            int x = i + dx[z];
            int y = j + dy[z];
            if(x < 1 || x > n ||  y < 1 || y > m)
            {
                continue;
            }
            if(a[x][y] =='#' || dict[make_pair( make_pair(x , y), kay + 1)])
            {
                continue;
            }
            dict[make_pair( make_pair(x , y), kay + 1)] = true;
            q.push(TrangThai(x , y , kay + 1));
        }


    }

    cout << res;

    return 0;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 57036 KB Output is correct
2 Correct 20 ms 4052 KB Output is correct
3 Correct 5 ms 1472 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 57036 KB Output is correct
2 Correct 20 ms 4052 KB Output is correct
3 Correct 5 ms 1472 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 563 ms 62732 KB Output is correct
8 Correct 96 ms 11532 KB Output is correct
9 Correct 18 ms 2880 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 731 ms 63932 KB Output is correct
13 Correct 821 ms 47476 KB Output is correct
14 Correct 419 ms 29884 KB Output is correct
15 Correct 11 ms 1876 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 835 ms 64408 KB Output is correct
18 Correct 654 ms 51784 KB Output is correct
19 Correct 207 ms 22812 KB Output is correct
20 Correct 68 ms 8232 KB Output is correct
21 Correct 3 ms 596 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 57036 KB Output is correct
2 Correct 20 ms 4052 KB Output is correct
3 Correct 5 ms 1472 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 563 ms 62732 KB Output is correct
8 Correct 96 ms 11532 KB Output is correct
9 Correct 18 ms 2880 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 731 ms 63932 KB Output is correct
13 Correct 821 ms 47476 KB Output is correct
14 Correct 419 ms 29884 KB Output is correct
15 Correct 11 ms 1876 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 835 ms 64408 KB Output is correct
18 Correct 654 ms 51784 KB Output is correct
19 Correct 207 ms 22812 KB Output is correct
20 Correct 68 ms 8232 KB Output is correct
21 Correct 3 ms 596 KB Output is correct
22 Execution timed out 1105 ms 237432 KB Time limit exceeded
23 Halted 0 ms 0 KB -