oj.uz

Submission #478994

# Submission time Handle Problem Language Result Execution time Memory
478994 2021-10-09T10:48:31 Z nicolaalexandra Furniture (JOI20_furniture) C++14
100 / 100
 2099 ms 15868 KB 
#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

int a[DIM][DIM],viz[DIM][DIM],cnt[DIM*2];
int n,m,i,j,q,x,y;

void mark (int i, int j){
    if (i <= 0 || i > n || j <= 0 || j > m)
        return;
    if (a[i][j])
        return;

    a[i][j] = 1;
    cnt[i+j]--;

    if (i == 1 || j == m || a[i-1][j+1]){
        mark (i,j+1);
        mark (i-1,j);
    }

    if (i == n || j == 1 || a[i+1][j-1]){
        mark (i+1,j);
        mark (i,j-1);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;

    /// cnt[i] - in cate locuri de pe diagonala secundara i pot sa ajung

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            cnt[i+j]++;

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            cin>>x;
            if (x)
                mark (i,j);
        }

    cin>>q;
    for (;q--;){
        cin>>x>>y;
        if (a[x][y]){
            cout<<"1\n";
            continue;
        }
        if (cnt[x+y] == 1){
            cout<<"0\n";
            continue;
        }
        cout<<"1\n";
        mark(x,y);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 9 ms 716 KB Output is correct
3 Correct 9 ms 696 KB Output is correct
4 Correct 17 ms 724 KB Output is correct
5 Correct 18 ms 760 KB Output is correct
6 Correct 21 ms 752 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 21 ms 716 KB Output is correct
9 Correct 30 ms 764 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 9 ms 716 KB Output is correct
3 Correct 9 ms 696 KB Output is correct
4 Correct 17 ms 724 KB Output is correct
5 Correct 18 ms 760 KB Output is correct
6 Correct 21 ms 752 KB Output is correct
7 Correct 20 ms 760 KB Output is correct
8 Correct 21 ms 716 KB Output is correct
9 Correct 30 ms 764 KB Output is correct
10 Correct 53 ms 684 KB Output is correct
11 Correct 12 ms 460 KB Output is correct
12 Correct 703 ms 4916 KB Output is correct
13 Correct 190 ms 4324 KB Output is correct
14 Correct 1679 ms 5844 KB Output is correct
15 Correct 1677 ms 5896 KB Output is correct
16 Correct 1858 ms 12768 KB Output is correct
17 Correct 2008 ms 15584 KB Output is correct
18 Correct 1908 ms 14940 KB Output is correct
19 Correct 2099 ms 15868 KB Output is correct
20 Correct 1966 ms 15760 KB Output is correct
21 Correct 2021 ms 15772 KB Output is correct