oj.uz

Submission #757625

# Submission time Handle Problem Language Result Execution time Memory
757625 2023-06-13T13:03:11 Z Hanksburger Furniture (JOI20_furniture) C++17
100 / 100
 372 ms 15932 KB 
#include <bits/stdc++.h>
using namespace std;
int a[1005][1005], cnt[2005], visited[1005][1005], n, m, o;
queue<pair<int, int> > q;
int f(int x, int y)
{
    return (1<=x && x<=n && 1<=y && y<=m);
}
void g()
{
    while (!q.empty())
    {
        int ux=q.front().first, uy=q.front().second;
        q.pop();
        if (a[ux-1][uy+1])
        {
            if (f(ux-1, uy) && !a[ux-1][uy])
            {
                a[ux-1][uy]=1;
                cnt[ux+uy-1]--;
                q.push({ux-1, uy});
            }
            if (f(ux, uy+1) && !a[ux][uy+1])
            {
                a[ux][uy+1]=1;
                cnt[ux+uy+1]--;
                q.push({ux, uy+1});
            }
        }
        if (a[ux+1][uy-1])
        {
            if (f(ux+1, uy) && !a[ux+1][uy])
            {
                a[ux+1][uy]=1;
                cnt[ux+uy+1]--;
                q.push({ux+1, uy});
            }
            if (f(ux, uy-1) && !a[ux][uy-1])
            {
                a[ux][uy-1]=1;
                cnt[ux+uy-1]--;
                q.push({ux, uy-1});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i=0; i<=m+1; i++)
        a[0][i]=a[n+1][i]=1;
    for (int i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]=1;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin >> a[i][j];
            if (a[i][j])
                q.push({i, j});
            else
                cnt[i+j]++;
        }
    }
    g();
    cin >> o;
    for (int i=1; i<=o; i++)
    {
        int x, y;
        cin >> x >> y;
        if (a[x][y])
            cout << 1 << '\n';
        else if (cnt[x+y]==1)
            cout << 0 << '\n';
        else
        {
            cout << 1 << '\n';
            a[x][y]=1;
            cnt[x+y]--;
            q.push({x, y});
            g();
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 8 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 138 ms 7252 KB Output is correct
13 Correct 51 ms 6760 KB Output is correct
14 Correct 288 ms 13928 KB Output is correct
15 Correct 292 ms 13704 KB Output is correct
16 Correct 299 ms 14688 KB Output is correct
17 Correct 337 ms 15508 KB Output is correct
18 Correct 292 ms 14996 KB Output is correct
19 Correct 341 ms 15836 KB Output is correct
20 Correct 247 ms 15916 KB Output is correct
21 Correct 372 ms 15932 KB Output is correct