oj.uz

Submission #294698

# Submission time Handle Problem Language Result Execution time Memory
294698 2020-09-09T08:36:40 Z Alexa2001 Furniture (JOI20_furniture) C++17
0 / 100
 9 ms 8448 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;

int a[Nmax][Nmax];
int diag[2*Nmax];
int n, m;


queue<pair<int,int>> q;


void verif(int x, int y)
{
    if(a[x][y]) return;

    if( (a[x+1][y] && a[x][y+1] && x+y < n+m) || (a[x-1][y] && a[x][y-1] && x+y > 1+1) )
        q.push({x, y});
}

void moare(int x, int y)
{
    q.push({x, y});

    while(q.size())
    {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        a[x][y] = 1;
        --diag[x+y];

        verif(x+1, y);
        verif(x, y+1);
        verif(x-1, y);
        verif(x, y-1);
    }
}

int solve(int x, int y)
{
    if(a[x][y] == 1) return 1;
    if(diag[x+y] == 1) return 0;

    moare(x, y);

    return 1;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> m;

    int i, j;

    for(i=0; i<=1001; ++i) a[i][0] = a[0][i] = a[n+1][i] = a[i][m+1] = 1;

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

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            cin >> a[i][j];
            if(a[i][j])
            {
                a[i][j] = 0;
                assert(solve(i, j));
            }
        }

    int q;
    cin >> q;
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        cout << solve(x, y) << '\n';
    }

    return 0;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Runtime error 9 ms 8448 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Runtime error 9 ms 8448 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -