Submission #328922

#	Time	Username	Problem	Language	Result	Execution time	Memory
328922		egas	Nautilus (BOI19_nautilus)	C++14	100 / 100	206 ms	1260 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

template<size_t TT >

void set_bit(bitset<TT> &x,int idx,int val) {

    x[x.size()-idx-1]=val;

}

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int r;

    cin >> r;

    int c;

    cin >> c;

    int m;

    cin >> m;

    vector<string> grid;

    for(int i = 0 ; i < r ; i++) {

        string temp;

        cin >> temp;

        grid.push_back(temp);

    }

    string path;

    cin >> path;

    vector<bitset<501>> isValid(501);

    for(int i = 0 ; i < r ; i++) {

        for(int j = 0 ; j < c ; j++) {

            if(grid[i][j]=='.') {

                set_bit(isValid[i],j,1);

            }

        }

    }

    vector<vector<bitset<501>>> canVisit(2,vector<bitset<501>>(501));

    int res=0;

    for(int i = 0 ; i < r ; i++) {

        for(int j = 0 ; j < c ; j++) {

            if(grid[i][j]=='.') {

                set_bit(canVisit[0][i],j,1);

            }

        }

    }

    for(int k=0; k<path.length(); k++) {

        if(path[k]=='S') {

            for(int i = 0 ; i < r ; i++) {

                if(i-1>=0)

                    canVisit[1][i]=(canVisit[0][(i-1)])&isValid[i];

            }

        } else if(path[k]=='N') {

            for(int i = 0 ; i < r ; i++) {

                if(i+1<r)

                    canVisit[1][i]=(canVisit[0][(i+1)])&isValid[i];

            }

        } else if(path[k]=='E') {

            for(int i = 0 ; i < r ; i++) {

                canVisit[1][i]=(canVisit[0][i]>>1)&isValid[i];

            }

        } else if(path[k]=='W') {

            for(int i = 0 ; i < r ; i++) {

                canVisit[1][i]=(canVisit[0][i]<<1)&isValid[i];

            }

        } else {

            for(int i = 0 ; i < r ; i++) {

                canVisit[1][i]=(canVisit[0][i]<<1)&isValid[i];

                canVisit[1][i]|=(canVisit[0][i]>>1)&isValid[i];

                if(i-1>=0)

                    canVisit[1][i]|=(canVisit[0][(i-1)])&isValid[i];

                if(i+1<r)

                    canVisit[1][i]|=(canVisit[0][(i+1)])&isValid[i];

            }

        }

        for(int i = 0 ; i < r ; i++) {

            canVisit[0][i] = canVisit[1][i];

            canVisit[1][i].reset();

        }

    }

    for(int i = 0 ; i < r ; i++) {

        for(int j = 0 ; j < c ; j++) {

            res+=canVisit[0][i][501-j-1];

        }

    }

    cout << res << '\n';

    return 0;

}

Compilation message (stderr)

nautilus.cpp: In function 'int32_t main()':
nautilus.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int k=0; k<path.length(); k++) {
      |                  ~^~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34