Submission #552580

#	Time	Username	Problem	Language	Result	Execution time	Memory
552580		ollel	Nautilus (BOI19_nautilus)	C++14	29 / 100	2 ms	404 KiB

nautilus

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

int rows, cols, m;

string commands;

const int maxrows = 501;
vector<bitset<maxrows>> blocked(maxrows);
vector<bitset<maxrows>> yes(maxrows), nyes(maxrows);

int main() {
  cin >> rows >> cols >> m;

  blocked.resize(rows);
  rep(r,0,rows) blocked[r].reset();

    rep(r,0,rows) {
    string s; cin >> s;
    rep(c,0,cols) {
      if (s[c] == '.') blocked[r].set(c);
    }
  }
  cin >> commands;

  rep(r,0,rows) yes[r] = blocked[r];

  for (int i = m - 1; i >= 0; i--) {
  // for (int i = 0; i < m; i++) {

    rep(r,0,rows) nyes[r].reset();
    if (commands[i] == 'E') {
      rep(r,0,rows) nyes[r] = (yes[r] >> 1) & blocked[r];
    }
    if (commands[i] == 'W') {
      rep(r,0,rows) nyes[r] = (yes[r] << 1) & blocked[r];
    }
    if (commands[i] == 'S') {
      if (rows == 1) {cout << 0 << endl; exit(0);}
      rep(r,0,rows - 1) nyes[r] = yes[r + 1] & blocked[r];
    }
    if (commands[i] == 'N') {
      if (rows == 1) {cout << 0 << endl; exit(0);}
      rep(r,1,rows) nyes[r] = yes[r - 1] & blocked[r];
    }
    if (commands[i] == '?') {
      if (rows == 1 && cols == 1) {
        cout << 0 << endl;
        exit(0);
      }
      else if (rows == 1) {
        nyes[0] = ((yes[0] >> 1) | (yes[0] << 1)) & blocked[0];
      } else {
        nyes[0] = (yes[1] | (yes[0] >> 1) | (yes[0] << 1)) & blocked[0];
        rep(r,1,rows - 1) {
          nyes[r] = (yes[r + 1] | yes[r - 1] | (yes[r] >> 1) | (yes[r] << 1)) & blocked[r];
        }
        nyes[rows - 1] = (yes[rows - 2] | (yes[rows - 1] >> 1) | (yes[rows - 1] << 1)) & blocked[rows - 1];
      }
    }
    rep(r,0,rows) yes[r] = nyes[r];

    // cout << commands[i] << endl;
    // rep(r,0,rows) {
    //   rep(c,0,cols) cout << yes[r].test(c);
    //   cout << endl;
    // }
    // cout << endl;


  }
  int ans = 0;
  rep(r,0,rows) rep(c,0,cols) if (yes[r].test(c)) ans++;
  cout << ans << endl;
}

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