oj.uz

Submission #123012

# Submission time Handle Problem Language Result Execution time Memory
123012 2019-06-30T01:45:38 Z model_code Nautilus (BOI19_nautilus) C++17
100 / 100
 273 ms 1088 KB 
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int r,c,m;
vector<string> grid;
bool valid_pos(int i, int j){
    return !(i < 0 || j < 0 || i >= r || j >= c || grid[i][j] == '#');
}
int main(){
    cin >> r >> c >> m;
    grid.resize(r);
    for(int i = 0; i < r; ++i)
        cin >> grid[i];
    string msg;
    cin >> msg;
    bitset<1000> reach[r],tmp[r],sea[r];
    for(int i = 0; i < r; ++i){
        for(int j = 0; j < c; ++j){
            sea[i][j] = grid[i][c-1-j] == '.';
            reach[i][j] = grid[i][c-1-j] == '.';
        }
    }
    for(char w : msg){
        for(int i = 0; i < r; ++i){
            if(w == 'W')
                reach[i] = (reach[i]<<1)&sea[i];
            if(w == 'E')
                reach[i] = (reach[i]>>1)&sea[i];
            if(w == 'N')
                if(i+1 < r)
                    reach[i] = reach[i+1]&sea[i];
                else
                    reach[i].reset();
            if(w == '?'){
                tmp[i] = (reach[i]<<1)|(reach[i]>>1);
                if(i)
                    tmp[i] |= reach[i-1];
                if(i+1 < r)
                    tmp[i] |= reach[i+1];
                tmp[i] &= sea[i];
            }
        }
        for(int i = r-1; i >= 0; --i)
            if(w == 'S')
                if(i)
                    reach[i] = reach[i-1]&sea[i];
                else
                    reach[i].reset();
        for(int i = 0; i < r; ++i)
            if(w == '?')
                reach[i] = tmp[i];
    }
    int ans = 0;
    for(int i = 0; i < r; ++i)
        ans += reach[i].count();
    cout << ans << '\n';
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:30:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(w == 'N')
               ^
nautilus.cpp:45:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(w == 'S')
               ^

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 148 ms 1052 KB Output is correct
23 Correct 151 ms 1016 KB Output is correct
24 Correct 146 ms 1016 KB Output is correct
25 Correct 146 ms 1052 KB Output is correct
26 Correct 145 ms 1016 KB Output is correct
27 Correct 215 ms 1080 KB Output is correct
28 Correct 219 ms 1016 KB Output is correct
29 Correct 217 ms 1016 KB Output is correct
30 Correct 218 ms 1020 KB Output is correct
31 Correct 214 ms 1084 KB Output is correct
32 Correct 270 ms 988 KB Output is correct
33 Correct 270 ms 1016 KB Output is correct
34 Correct 270 ms 1016 KB Output is correct
35 Correct 273 ms 1088 KB Output is correct
36 Correct 271 ms 1016 KB Output is correct