Submission #444778

#	Time	Username	Problem	Language	Result	Execution time	Memory
444778		prvocislo	Nautilus (BOI19_nautilus)	C++17	100 / 100	146 ms	776 KiB

nautilus

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 505;
int r, c, m;
vector<bitset<maxn> > v(maxn); // povodne pole
void w(vector<bitset<maxn> > &b)
{
    for (int i = 0; i < r; i++) b[i] >>= 1;
}
void e(vector<bitset<maxn> > &b)
{
    for (int i = 0; i < r; i++) b[i] <<= 1;
}
void n(vector<bitset<maxn> > &b)
{
    for (int i = 0; i < r; i++) b[i] = b[i+1];
}
void s(vector<bitset<maxn> > &b)
{
    for (int i = r-1; i > 0; i--) b[i] = b[i-1];
    b[0] = 0;
}
void fix(vector<bitset<maxn> > &b)
{
    for (int i = 0; i < r; i++) b[i] &= v[i];
}
void print(vector<bitset<maxn> > &b)
{
    cout << "\n=============\n";
    for (int i = 0; i < r; i++)
    {
       for (int j = 0; j < c; j++) cout << b[i][j];
       cout << "\n";
    }
    cout << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c >> m;
    for (int i = 0; i < r; i++)
    {
        string vi; cin >> vi;
        for (int j = 0; j < c; j++) 
            if (vi[j] == '.') v[i][j] = 1;
    }
    //print(v);
    string st; cin >> st;
    vector<bitset<maxn> > b = v;
    //print(b);
    for (char ch : st)
    {
        if (ch == 'N') n(b);
        if (ch == 'E') e(b);
        if (ch == 'S') s(b);
        if (ch == 'W') w(b);
        if (ch == '?') // mozeme urobit lubovolny zo styroch krokov
        {
            vector<bitset<maxn> > nw[4];
            for (int j = 0; j < 4; j++) nw[j] = b;
            n(nw[0]), e(nw[1]), s(nw[2]), w(nw[3]);
            for (int j = 0; j < r; j++) for (int k = 1; k < 4; k++) nw[0][j] |= nw[k][j];
            b = nw[0];
        }
        fix(b);
        //print(b);
    }
    //print(b);
    int ans = 0;
    for (int i = 0; i < r; i++)
        ans += b[i].count();
    cout << ans << "\n";
    return 0;
}

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