oj.uz

Submission #819098

# Submission time Handle Problem Language Result Execution time Memory
819098 2023-08-10T08:01:04 Z 이성호(#10133) Virus Experiment (JOI19_virus) C++17
14 / 100
 49 ms 10316 KB 
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
int cnt[16];
bool inc(char c, int pv)
{
    if (c == 'W') return pv >> 1 & 1;
    else return pv >> 3 & 1;
}
bool infected[805][805];
int arr[805][805];
bool rht[805][805];
bool lft[805][805];
bool idrht[805][805], idlft[805][805];
int num[805][805];
int cpx[805][805];
bool act[805][805];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int M, R, C; cin >> M >> R >> C;
    string D; cin >> D; D += D;
    for (int i = 0; i < 16; i++) {
        if (i & 1 || i >> 2 & 1) continue;
        for (int j = 0; j < 2*M; j++) {
            if (!inc(D[j], i)) continue;
            int s = j;
            while (j + 1 < 2*M && inc(D[j+1], i)) j++;
            int e = j;
            cnt[i] = max(cnt[i], e - s + 1);
        }
        if (cnt[i] >= M) cnt[i] = 100000;
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) arr[i][j] = 200001;
        }
    }
    auto chk = [&](int i, int j){return 0 <= i && i < R && 0 <= j && j < C;};
    auto state = [&](int i, int j)
    {
        int ans = 0;
        if (chk(i, j-1)) ans |= (int)infected[i][j-1] << 1;
        if (chk(i, j+1)) ans |= (int)infected[i][j+1] << 3;
        return ans;
    };
    int mn = R * C + 1, mncnt = -1;
    for (int row = 0; row < R; row++) {
        for (int i = 0; i < C - 1; i++) {
            if (cnt[2] >= arr[row][i+1]) rht[row][i] = true;
            if (cnt[8] >= arr[row][i]) lft[row][i] = true;
        }
        int idx = 0;
        for (int i = 0; i < C; i++) {
            cpx[row][i] = idx;
            while (i + 1 < C && lft[row][i] && rht[row][i]) cpx[row][++i] = idx;
            idx++;
        }
        for (int i = 0; i < C; i++) {
            num[row][cpx[row][i]]++;
            if (arr[row][i] == 200001) act[row][cpx[row][i]] = true;
            if (i < C - 1 && cpx[row][i] != cpx[row][i+1]) {
                idrht[row][cpx[row][i]] = rht[row][i];
                idlft[row][cpx[row][i]] = lft[row][i];
            }
        }
        for (int i = 0; i < idx; i++) {
            if (act[row][i]) continue;
            if (i < idx - 1 && idrht[row][i]) continue;
            if (i > 0 && idlft[row][i-1]) continue;
            if (mn > num[row][i]) {
                mn = num[row][i];
                mncnt = num[row][i];
            }
            else if (mn == num[row][i]) {
                mncnt += num[row][i];
            }
        }
    }
    cout << mn << '\n' << mncnt << '\n';
    return 0;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:43:10: warning: variable 'state' set but not used [-Wunused-but-set-variable]
   43 |     auto state = [&](int i, int j)
      |          ^~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 38 ms 10316 KB Output is correct
3 Correct 49 ms 9736 KB Output is correct
4 Correct 46 ms 9688 KB Output is correct
5 Correct 47 ms 9720 KB Output is correct
6 Correct 3 ms 8404 KB Output is correct
7 Correct 49 ms 9468 KB Output is correct
8 Correct 20 ms 6740 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 38 ms 10316 KB Output is correct
3 Correct 49 ms 9736 KB Output is correct
4 Correct 46 ms 9688 KB Output is correct
5 Correct 47 ms 9720 KB Output is correct
6 Correct 3 ms 8404 KB Output is correct
7 Correct 49 ms 9468 KB Output is correct
8 Correct 20 ms 6740 KB Output is correct
9 Incorrect 0 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -