oj.uz

Submission #516305

# Submission time Handle Problem Language Result Execution time Memory
516305 2022-01-21T04:49:59 Z qwerasdfzxcl Furniture (JOI20_furniture) C++14
100 / 100
 606 ms 23844 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[1010][1010], dp1[1010][1010], dp2[1010][1010], cnt[2020];

void debug(int n, int m){
    printf("DEBUG\n");
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) printf("%d ", dp1[i][j]);
        printf("\n");
    }

    printf("\n");
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) printf("%d ", dp2[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
    }

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            dp1[i][j] = dp1[i][j-1] | dp1[i-1][j];
            if (a[i][j]) dp1[i][j] = 0;
            dp1[1][1] = 1;
        }
    }
    for (int i=n;i;i--){
        for (int j=m;j;j--){
            dp2[i][j] = dp2[i][j+1] | dp2[i+1][j];
            if (a[i][j]) dp2[i][j] = 0;
            dp2[n][m] = 1;
        }
    }

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (dp1[i][j] && dp2[i][j]) cnt[i+j]++;
    }

    //debug(n, m);


    int q;
    scanf("%d", &q);
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (cnt[x+y]==1 && dp1[x][y] && dp2[x][y]) {printf("0\n"); continue;}
        printf("1\n");
        a[x][y] = 1;

        queue<pair<int, int>> q;
        q.emplace(x, y);
        while(!q.empty()){
            auto p = q.front(); q.pop();
            if (!dp1[p.first][p.second]) continue;
            if (!a[p.first][p.second] && (dp1[p.first-1][p.second] || dp1[p.first][p.second-1])) continue;
            dp1[p.first][p.second] = 0;
            if (dp2[p.first][p.second]) cnt[p.first+p.second]--;

            if (p.first+1<=n) q.emplace(p.first+1, p.second);
            if (p.second+1<=m) q.emplace(p.first, p.second+1);
        }

        q.emplace(x, y);
        while(!q.empty()){
            auto p = q.front(); q.pop();
            if (!dp2[p.first][p.second]) continue;
            if (!a[p.first][p.second] && (dp2[p.first+1][p.second] || dp2[p.first][p.second+1])) continue;
            dp2[p.first][p.second] = 0;
            if (dp1[p.first][p.second]) cnt[p.first+p.second]--;

            if (p.first-1>0) q.emplace(p.first-1, p.second);
            if (p.second-1>0) q.emplace(p.first, p.second-1);
        }

        //debug(n, m);
    }
    return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:26:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
      |                                ~~~~~^~~~~~~~~~~~~~
furniture.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 4 ms 1356 KB Output is correct
4 Correct 4 ms 1336 KB Output is correct
5 Correct 5 ms 1484 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 5 ms 1480 KB Output is correct
9 Correct 5 ms 1484 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 4 ms 1356 KB Output is correct
4 Correct 4 ms 1336 KB Output is correct
5 Correct 5 ms 1484 KB Output is correct
6 Correct 5 ms 1484 KB Output is correct
7 Correct 5 ms 1484 KB Output is correct
8 Correct 5 ms 1480 KB Output is correct
9 Correct 5 ms 1484 KB Output is correct
10 Correct 14 ms 1076 KB Output is correct
11 Correct 4 ms 864 KB Output is correct
12 Correct 300 ms 16604 KB Output is correct
13 Correct 73 ms 13380 KB Output is correct
14 Correct 507 ms 21028 KB Output is correct
15 Correct 533 ms 20988 KB Output is correct
16 Correct 603 ms 22264 KB Output is correct
17 Correct 606 ms 23324 KB Output is correct
18 Correct 540 ms 22696 KB Output is correct
19 Correct 566 ms 23676 KB Output is correct
20 Correct 387 ms 23732 KB Output is correct
21 Correct 551 ms 23844 KB Output is correct