oj.uz

Submission #1031750

# Submission time Handle Problem Language Result Execution time Memory
1031750 2024-07-23T06:32:14 Z 김은성(#10960) Furniture (JOI20_furniture) C++17
100 / 100
 220 ms 13996 KB 
#include <bits/stdc++.h>
using namespace std;
bool ch[1009][1009], ch2[1009][1009];
int n, m, cnt[2019];
void update(int r, int c){
    if(r<=0 || r>n || c<=0 || c>m || !ch[r][c])
        return;
    cnt[r+c] -= (ch[r][c] && ch2[r][c]);
    ch[r][c] = (ch[r-1][c] || ch[r][c-1]) && ch[r][c];
    cnt[r+c] += (ch[r][c] && ch2[r][c]);
    if(ch[r][c])
        return;
    update(r+1, c);
    update(r, c+1);
}
void update2(int r, int c){
    if(r<=0 || r>n || c<=0 || c>m || !ch2[r][c])
        return;
    cnt[r+c] -= (ch[r][c] && ch2[r][c]);
    ch2[r][c] = (ch2[r+1][c] || ch2[r][c+1]) && ch2[r][c];
    cnt[r+c] += (ch[r][c] && ch2[r][c]);
    if(ch2[r][c])
        return;
    update2(r-1, c);
    update2(r, c-1);
}
int main(){
    int i, j, r, c;
    scanf("%d %d", &n,&m);
    ch[0][1] = ch[1][0] = ch[n+1][m] = ch[n][m+1] = 1;
    ch2[0][1] = ch2[1][0] = ch2[n+1][m] = ch2[n][m+1] = 1;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            int val;
            scanf("%d", &val);
            if(!val){
                ch[i][j] = ch2[i][j] = 1;
            }
        }
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            ch[i][j] = ((ch[i-1][j] || ch[i][j-1]) && ch[i][j]);
        }
    }
    for(i=n; i>=1; i--){
        for(j=m; j>=1; j--){
            ch2[i][j] = ((ch2[i+1][j] || ch2[i][j+1]) && ch2[i][j]);
            if(ch[i][j] && ch2[i][j]){
                cnt[i+j]++;
            }
        }
    }
    int q;
    scanf("%d", &q);
    while(q--){
        scanf("%d %d", &r, &c);
        if(!(ch[r][c] && ch2[r][c]) || cnt[r+c] > 1){
            printf("1\n");
            cnt[r+c] -= (ch[r][c] && ch2[r][c]);
            ch[r][c] = ch2[r][c] = 0;
            update(r+1, c), update(r, c+1);
            update2(r-1, c), update2(r, c-1);
        }
        else
            printf("0\n");
    }
    return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |             scanf("%d", &val);
      |             ~~~~~^~~~~~~~~~~~
furniture.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d", &r, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 680 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 704 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 3 ms 604 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 680 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 704 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 8 ms 856 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 128 ms 6984 KB Output is correct
13 Correct 50 ms 4164 KB Output is correct
14 Correct 176 ms 11608 KB Output is correct
15 Correct 194 ms 11876 KB Output is correct
16 Correct 211 ms 12896 KB Output is correct
17 Correct 220 ms 13612 KB Output is correct
18 Correct 211 ms 13140 KB Output is correct
19 Correct 209 ms 13908 KB Output is correct
20 Correct 201 ms 13996 KB Output is correct
21 Correct 206 ms 13908 KB Output is correct