oj.uz

Submission #845894

# Submission time Handle Problem Language Result Execution time Memory
845894 2023-09-06T17:53:45 Z mickey080929 Sandwich (JOI16_sandwich) C++17
35 / 100
 8000 ms 3412 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[410][410];
int vis[410][410];
int chk[410][410];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int dfs(int x, int y, int d) {
    vis[x][y] = d;
    for (int i=0; i<2; i++) {
        int t = (d<<1) + a[x][y] + i; if (t >= 4) t -= 4;
        int nx = x + dx[t];
        int ny = y + dy[t];
        if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
        int nd = (t >= a[nx][ny] && t <= 1+a[nx][ny]) ^ 1;
        if (vis[nx][ny] == nd) {
            if (chk[nx][ny]) continue;
            return 0;
        }
        if (vis[nx][ny] == (nd ^ 1)) return 0;
        if (!dfs(nx, ny, nd)) return 0;
    }
    chk[x][y] = 1;
    return 1;
}

int solve(int sx, int sy, int sd) {
    memset(vis, -1, sizeof(vis));
    memset(chk, 0, sizeof(chk));
    if (!dfs(sx, sy, sd)) return -1;
    int ans = 0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            ans += (vis[i][j] != -1);
        }
    }
    return ans << 1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            char c;
            scanf(" %c", &c);
            if (c == 'N') a[i][j] = 0;
            else a[i][j] = 1;
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            int t1 = solve(i, j, 0), t2 = solve(i, j, 1);
            if (t1 == -1) printf("%d ", t2);
            else if (t2 == -1) printf("%d ", t1);
            else printf("%d ", min(t1, t2));
        }
        printf("\n");
    }
}

Compilation message

sandwich.cpp: In function 'int main()':
sandwich.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 3 ms 1628 KB Output is correct
4 Correct 1 ms 1724 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 102 ms 1628 KB Output is correct
7 Correct 170 ms 1848 KB Output is correct
8 Correct 187 ms 1628 KB Output is correct
9 Correct 119 ms 1880 KB Output is correct
10 Correct 186 ms 1836 KB Output is correct
11 Correct 199 ms 1836 KB Output is correct
12 Correct 98 ms 1808 KB Output is correct
13 Correct 222 ms 1876 KB Output is correct
14 Correct 212 ms 1856 KB Output is correct
15 Correct 158 ms 1624 KB Output is correct
16 Correct 149 ms 1628 KB Output is correct
17 Correct 151 ms 1628 KB Output is correct
18 Correct 151 ms 1628 KB Output is correct
19 Correct 154 ms 1824 KB Output is correct
20 Correct 149 ms 1880 KB Output is correct
21 Correct 139 ms 1624 KB Output is correct
22 Correct 143 ms 1832 KB Output is correct
23 Correct 146 ms 1624 KB Output is correct
24 Correct 217 ms 2140 KB Output is correct
25 Correct 209 ms 1836 KB Output is correct
26 Correct 224 ms 2096 KB Output is correct
27 Correct 210 ms 1628 KB Output is correct
28 Correct 218 ms 1624 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 3 ms 1628 KB Output is correct
4 Correct 1 ms 1724 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 102 ms 1628 KB Output is correct
7 Correct 170 ms 1848 KB Output is correct
8 Correct 187 ms 1628 KB Output is correct
9 Correct 119 ms 1880 KB Output is correct
10 Correct 186 ms 1836 KB Output is correct
11 Correct 199 ms 1836 KB Output is correct
12 Correct 98 ms 1808 KB Output is correct
13 Correct 222 ms 1876 KB Output is correct
14 Correct 212 ms 1856 KB Output is correct
15 Correct 158 ms 1624 KB Output is correct
16 Correct 149 ms 1628 KB Output is correct
17 Correct 151 ms 1628 KB Output is correct
18 Correct 151 ms 1628 KB Output is correct
19 Correct 154 ms 1824 KB Output is correct
20 Correct 149 ms 1880 KB Output is correct
21 Correct 139 ms 1624 KB Output is correct
22 Correct 143 ms 1832 KB Output is correct
23 Correct 146 ms 1624 KB Output is correct
24 Correct 217 ms 2140 KB Output is correct
25 Correct 209 ms 1836 KB Output is correct
26 Correct 224 ms 2096 KB Output is correct
27 Correct 210 ms 1628 KB Output is correct
28 Correct 218 ms 1624 KB Output is correct
29 Correct 20 ms 1796 KB Output is correct
30 Correct 21 ms 2428 KB Output is correct
31 Correct 6558 ms 3412 KB Output is correct
32 Correct 6502 ms 3112 KB Output is correct
33 Correct 1710 ms 2764 KB Output is correct
34 Execution timed out 8007 ms 3092 KB Time limit exceeded
35 Halted 0 ms 0 KB -