Submission #306184

#	Time	Username	Problem	Language	Result	Execution time	Memory
306184		dsabolic	Furniture (JOI20_furniture)	C++17	100 / 100	593 ms	24440 KiB

furniture

#include <bits/stdc++.h>

#define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))

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

using namespace std;
using pii = pair<int, int>;

const int N = 1e3 + 50;

int n, m;
int mat[N][N];
int dp[N][N];
int dp2[N][N];
int dig[2 * N];

void purge(int i, int j) {
        dp[i][j] = 0;
        if(dp2[i][j]) dig[i + j]--;

        for(int x = 0; x < 2; ++x) {
                int nx = i + -dx[x], ny = j + -dy[x];

                if(nx < 0 || ny < 0) continue;

                if(dp[nx][ny] == 1) {
                        purge(nx, ny);
                } else if(dp[nx][ny] == 2) {
                        dp[nx][ny] = 1;
                }
        }
}

void purge2(int i, int j) {
        dp2[i][j] = 0;
        if(dp[i][j]) dig[i + j]--;

        for(int x = 0; x < 2; ++x) {
                int nx = i + dx[x], ny = j + dy[x];

                if(nx >= n || ny >= m) continue;

                if(dp2[nx][ny] == 1) purge2(nx, ny);
                else if(dp2[nx][ny] == 2) dp2[nx][ny]--;
        }
}

int main() {
        scanf("%d%d", &n, &m);

        rep(i, 0, n)
                rep(j, 0, m)
                        scanf("%d", &mat[i][j]);

        for(int i = n - 1; i >= 0; --i) {
                for(int j = m - 1; j >= 0; --j) {
                        if(i == n - 1 && j == m - 1) {
                                dp[i][j] = 1;
                                continue;
                        }
                        if(mat[i][j] == 1) continue;

                        dp[i][j] = (dp[i + 1][j] > 0) + (dp[i][j + 1] > 0);
                }
        }
        for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j) {
                        if(!i && !j) {
                                dp2[i][j] = 1;
                                continue;
                        }
                        if(mat[i][j] == 1) continue;

                        if(i) dp2[i][j] += (dp2[i - 1][j] > 0);
                        if(j) dp2[i][j] += (dp2[i][j - 1] > 0);
                }
        }

        rep(i, 0, n) {
                rep(j, 0, m) {
                        //printf("%d ", dp[i][j]);
                        dig[i + j] += (dp[i][j] > 0 && dp2[i][j] > 0);
                        //if(i + j == 1) printf("dig %d\n", dig[i + j]);
                }
                //printf("\n");
        }

        int q;
        for(scanf("%d", &q); q; q--) {
                int x, y; scanf("%d%d", &x, &y);
                --x, --y;

                if(dig[x + y] == 1 && dp[x][y] && dp2[x][y]) {
                        printf("0\n");
                } else {
                        printf("1\n");

                        if(dp[x][y]) purge(x, y);
                        if(dp2[x][y]) purge2(x, y);
                }
        }

        return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
      |                              ^
furniture.cpp:53:9: note: in expansion of macro 'rep'
   53 |         rep(i, 0, n)
      |         ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
      |                              ^
furniture.cpp:54:17: note: in expansion of macro 'rep'
   54 |                 rep(j, 0, m)
      |                 ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
      |                              ^
furniture.cpp:81:9: note: in expansion of macro 'rep'
   81 |         rep(i, 0, n) {
      |         ^~~
furniture.cpp:3:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
      |                              ^
furniture.cpp:82:17: note: in expansion of macro 'rep'
   82 |                 rep(j, 0, m) {
      |                 ^~~
furniture.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:55:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |                         scanf("%d", &mat[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
furniture.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         for(scanf("%d", &q); q; q--) {
      |             ~~~~~^~~~~~~~~~
furniture.cpp:92:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |                 int x, y; scanf("%d%d", &x, &y);
      |                           ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95