oj.uz

Submission #491863

# Submission time Handle Problem Language Result Execution time Memory
491863 2021-12-04T20:45:23 Z jerzyk Furniture (JOI20_furniture) C++17
100 / 100
 846 ms 114556 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 1000 + 7;
int tab[N][N], tab2[N][N];
set<pair<int, int>> czy[N * N];

void Zmien(int i, int j)
{
    if(tab[i][j] == 1)
        return;
    tab[i][j] = 1;
    if(tab2[i][j] == 0)
        czy[i + j - 2].erase(make_pair(i, j));
    if(tab[i + 1][j - 1] == 1)
        Zmien(i + 1, j);
    if(tab[i - 1][j + 1] == 1)
        Zmien(i, j + 1);
}

void Zmien2(int i, int j)
{
    if(tab2[i][j] == 1)
        return;
    tab2[i][j] = 1;
    if(tab[i][j] == 0)
        czy[i + j - 2].erase(make_pair(i, j));
    if(tab2[i + 1][j - 1] == 1)
        Zmien2(i, j - 1);
    if(tab2[i - 1][j + 1] == 1)
        Zmien2(i - 1, j);
}

void Furniture()
{
    int n, q, m, x;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        tab[i][0] = 1;
        tab[i][m + 1] = 1;
        tab2[i][0] = 1;
        tab2[i][m + 1] = 1;
        for(int j = 1; j <= m; ++j)
        {
            tab[0][j] = 1;
            tab[n + 1][j] = 1;
            tab2[0][j] = 1;
            tab2[n + 1][j] = 1;
            czy[i + j - 2].insert(make_pair(i, j));
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            cin >> x;
            if(x == 1)
            {
                Zmien(i, j);
                Zmien2(i, j);
            }
        }
    }
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        int a, b;
        cin >> a >> b;
        if(czy[a + b - 2].size() == 1 && tab[a][b] == 0 && tab2[a][b] == 0)
        {
            cout << 0 << "\n";
        }else
        {
            cout << 1 << "\n";
            Zmien(a, b);
            Zmien2(a, b);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Furniture();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48736 KB Output is correct
2 Correct 32 ms 48996 KB Output is correct
3 Correct 28 ms 49076 KB Output is correct
4 Correct 30 ms 49328 KB Output is correct
5 Correct 34 ms 49228 KB Output is correct
6 Correct 35 ms 49324 KB Output is correct
7 Correct 29 ms 49300 KB Output is correct
8 Correct 29 ms 49236 KB Output is correct
9 Correct 29 ms 49228 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48736 KB Output is correct
2 Correct 32 ms 48996 KB Output is correct
3 Correct 28 ms 49076 KB Output is correct
4 Correct 30 ms 49328 KB Output is correct
5 Correct 34 ms 49228 KB Output is correct
6 Correct 35 ms 49324 KB Output is correct
7 Correct 29 ms 49300 KB Output is correct
8 Correct 29 ms 49236 KB Output is correct
9 Correct 29 ms 49228 KB Output is correct
10 Correct 39 ms 51340 KB Output is correct
11 Correct 27 ms 48856 KB Output is correct
12 Correct 658 ms 104804 KB Output is correct
13 Correct 370 ms 98348 KB Output is correct
14 Correct 723 ms 106716 KB Output is correct
15 Correct 722 ms 104756 KB Output is correct
16 Correct 674 ms 109224 KB Output is correct
17 Correct 701 ms 112532 KB Output is correct
18 Correct 846 ms 110740 KB Output is correct
19 Correct 682 ms 114408 KB Output is correct
20 Correct 566 ms 114556 KB Output is correct
21 Correct 634 ms 114444 KB Output is correct