Submission #757780

#	Time	Username	Problem	Language	Result	Execution time	Memory
757780		taher	Nautilus (BOI19_nautilus)	C++17	100 / 100	493 ms	2240 KiB

nautilus

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 500 + 1;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int r , c , m;
  cin >> r >> c >> m;
  vector<vector<char>> g(r , vector<char> (c));
  for (int i = 0 ; i < r ; i++) {
    for (int j = 0 ; j < c ; j++) {
      cin >> g[i][j];
    }
  }
  string s;
  cin >> s;
  vector<bitset<Maxn>> cur(r) , forbidden(r);
  bitset<Maxn> Fixer;
  for (int i = 0 ; i < c ; i++) {
    Fixer[i] = 1;
  }
  auto Move_Up = [&]() {
    vector<bitset<Maxn>> res(r);
    for (int i = 0 ; i < r - 1 ; i++) {
      res[i] |= cur[i + 1];
    }
    vector<bitset<Maxn>> t = res;
    for (int i = 0 ; i < r ; i++) {
      t[i] ^= forbidden[i];      
    }
    for (int i = 0 ; i < r ; i++) {
      res[i] &= t[i];
    }
    return res;
  };

  auto Move_Down = [&]() {
    vector<bitset<Maxn>> res(r);
    for (int i = 1 ; i < r ; i++) {
      res[i] |= cur[i - 1];
    }
    vector<bitset<Maxn>> t = res;
    for (int i = 0 ; i < r ; i++) {
      t[i] ^= forbidden[i];      
    }
    for (int i = 0 ; i < r ; i++) {
      res[i] &= t[i];
    }
    return res;
  };

  auto Move_Left = [&]() {
    vector<bitset<Maxn>> res(r);
    for (int i = 0 ; i < r ; i++) {
      res[i] = (cur[i] >> 1);
    }
    vector<bitset<Maxn>> t = res;
    for (int i = 0 ; i < r ; i++) {
      t[i] ^= forbidden[i];      
    }
    for (int i = 0 ; i < r ; i++) {
      res[i] &= t[i];
    }
    return res;
  };

  auto Move_Right = [&]() {
    vector<bitset<Maxn>> res(r);
    for (int i = 0 ; i < r ; i++) {
      res[i] = (cur[i] << 1);
    }
    vector<bitset<Maxn>> t = res;
    for (int i = 0 ; i < r ; i++) {
      t[i] ^= forbidden[i];      
    }
    for (int i = 0 ; i < r ; i++) {
      res[i] &= t[i];
    }
    return res;    
  };

  auto Fix = [&]() {
    for (int i = 0 ; i < r ; i++) {
      cur[i] &= Fixer;
    }
    return ;
  };

  for (int i = 0 ; i < r ; i++) {
    for (int j = 0 ; j < c ; j++) {
      if (g[i][j] != '#') cur[i][j] = true;
      else forbidden[i][j] = true;
    }
  }
  for (int idx = 0 ; idx < m ; idx++) {
    vector<bitset<Maxn>> res(r);
    if (s[idx] == 'N') {
      res = Move_Up();      
    }
    else if (s[idx] == 'S') {
      res = Move_Down();
    }
    else if (s[idx] == 'E') {
      res = Move_Right();
    }
    else if (s[idx] == 'W') {
      res = Move_Left();
    }
    else {
      vector<bitset<Maxn>> A = Move_Down();
      vector<bitset<Maxn>> B = Move_Left();
      vector<bitset<Maxn>> C = Move_Right();
      vector<bitset<Maxn>> D = Move_Up();
      for (int i = 0 ; i < r ; i++) {
        res[i] |= A[i];
        res[i] |= B[i];
        res[i] |= C[i];
        res[i] |= D[i];
      }
    } 
    swap(cur , res);
    Fix();
  }
  int ans = 0;
  for (int i = 0 ; i < r ; i++) {
    for (int j = 0 ; j < c ; j++) {
      if (cur[i][j]) {
        assert(g[i][j] != '#');
        ans += 1;
      }
    }
  }
  cout << ans << '\n';
  return 0; 
}

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