oj.uz

Submission #495648

# Submission time Handle Problem Language Result Execution time Memory
495648 2021-12-19T17:48:15 Z 600Mihnea Virus Experiment (JOI19_virus) C++17
100 / 100
 724 ms 25264 KB 
#include <bits/stdc++.h>

using namespace std;

int Transform(int x) {
  return x;
}

int codif(char ch) {
  if (ch == 'N') return Transform(0);
  if (ch == 'W') return Transform(1);
  if (ch == 'S') return Transform(2);
  if (ch == 'E') return Transform(3);
  assert(0);
}

mt19937 rng((long long) (new char));

const int M = 100000 + 7;
const int N = 800 + 7;
const int INF = (int) 1e9 + 7;
int mod;
int n;
int m;
string wind;
int res[N][N], mx[1 << 4], cur[1 << 4], when[N][N];
bool valid[N][N];

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, -1, 0, 1};

bool isOk(int r, int c) {
  if (min(r, c) < 1 || r > n || c > m) {
    return false;
  }
  if (res[r][c] == 0) {
    return false;
  }
  int whosValid = 0;
  for (int k = 0; k < 4; k++) {
    int rn = r + dr[k], cn = c + dc[k];
    if (valid[rn][cn]) {
      whosValid += (1 << k);
    }
  }
  return mx[whosValid] >= res[r][c];
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> mod >> n >> m >> wind;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> res[i][j];
    }
  }

  wind += wind;

  for (auto &ch : wind) {
    int current = codif(ch);
    for (int mask = 0; mask < (1 << 4); mask++) {
      if (mask & (1 << current)) {
        cur[mask]++;
        mx[mask] = max(mx[mask], cur[mask]);
      } else {
        cur[mask] = 0;
      }
    }
  }

  for (int mask = 0; mask < (1 << 4); mask++) {
    if (mx[mask] >= mod) {
      mx[mask] = INF;
    }
  }


  vector<pair<int, int>> ord;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (res[i][j]) {
        ord.push_back({i, j});
      }
    }
  }

  shuffle(ord.begin(), ord.end(), rng);


  int y = 0;
  for (auto &it : ord) {
    when[it.first][it.second] = ++y;
  }

  int Minimum = (int) 1e9, cnt = 0;

  for (auto &it : ord) {
    int rinit = it.first, cinit = it.second;
    bool Evalid = true;

    queue<pair<int, int>> q;
    vector<pair<int, int>> all;
    q.push({rinit, cinit});
    all.push_back({rinit, cinit});
    valid[rinit][cinit] = true;

    while (!q.empty() && Evalid) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      for (int k = 0; k < 4; k++) {
        int rn = r + dr[k], cn = c + dc[k];
        if (isOk(rn, cn) && !valid[rn][cn]) {
          q.push({rn, cn});
          all.push_back({rn, cn});
          valid[rn][cn] = true;
          if (when[rn][cn] < when[rinit][cinit]) {
            Evalid = false;
            break;
          }
        }
      }
    }


    for (auto &it : all) {
      valid[it.first][it.second] = 0;
    }

    if (!Evalid) {
      continue;
    }
    int current = (int) all.size();
    if (current < Minimum) {
      Minimum = current;
      cnt = 0;
    }
    cnt += (Minimum == current);
  }
  cout << Minimum << " " << cnt * Minimum << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 197 ms 11148 KB Output is correct
3 Correct 395 ms 11088 KB Output is correct
4 Correct 379 ms 12352 KB Output is correct
5 Correct 155 ms 14904 KB Output is correct
6 Correct 2 ms 4816 KB Output is correct
7 Correct 408 ms 12648 KB Output is correct
8 Correct 60 ms 7380 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 5 ms 716 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 7 ms 1020 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 5 ms 1008 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 7 ms 1008 KB Output is correct
14 Correct 6 ms 1008 KB Output is correct
15 Correct 6 ms 944 KB Output is correct
16 Correct 6 ms 1008 KB Output is correct
17 Correct 4 ms 844 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 6 ms 1008 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 197 ms 11148 KB Output is correct
3 Correct 395 ms 11088 KB Output is correct
4 Correct 379 ms 12352 KB Output is correct
5 Correct 155 ms 14904 KB Output is correct
6 Correct 2 ms 4816 KB Output is correct
7 Correct 408 ms 12648 KB Output is correct
8 Correct 60 ms 7380 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 7 ms 1020 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 5 ms 1008 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 3 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 2 ms 716 KB Output is correct
21 Correct 7 ms 1008 KB Output is correct
22 Correct 6 ms 1008 KB Output is correct
23 Correct 6 ms 944 KB Output is correct
24 Correct 6 ms 1008 KB Output is correct
25 Correct 4 ms 844 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 6 ms 1008 KB Output is correct
28 Correct 633 ms 25264 KB Output is correct
29 Correct 654 ms 24788 KB Output is correct
30 Correct 624 ms 19892 KB Output is correct
31 Correct 612 ms 15272 KB Output is correct
32 Correct 609 ms 13660 KB Output is correct
33 Correct 270 ms 12456 KB Output is correct
34 Correct 724 ms 24668 KB Output is correct
35 Correct 531 ms 16768 KB Output is correct
36 Correct 513 ms 12856 KB Output is correct
37 Correct 677 ms 16256 KB Output is correct
38 Correct 641 ms 24484 KB Output is correct
39 Correct 258 ms 13780 KB Output is correct
40 Correct 277 ms 13656 KB Output is correct
41 Correct 256 ms 12740 KB Output is correct
42 Correct 641 ms 18172 KB Output is correct
43 Correct 673 ms 25032 KB Output is correct
44 Correct 61 ms 7388 KB Output is correct