oj.uz

Submission #294704

# Submission time Handle Problem Language Result Execution time Memory
294704 2020-09-09T08:39:29 Z Alexa2001 Furniture (JOI20_furniture) C++17
100 / 100
 428 ms 16052 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]++;

    vector<pair<int,int>> need;

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

    for(auto it : need) assert( solve(it.first, it.second) );


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

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 6 ms 4352 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 5 ms 4352 KB Output is correct
5 Correct 5 ms 4352 KB Output is correct
6 Correct 6 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Correct 10 ms 4352 KB Output is correct
10 Correct 14 ms 4736 KB Output is correct
11 Correct 5 ms 4352 KB Output is correct
12 Correct 281 ms 9524 KB Output is correct
13 Correct 77 ms 7088 KB Output is correct
14 Correct 359 ms 14376 KB Output is correct
15 Correct 348 ms 14072 KB Output is correct
16 Correct 371 ms 14500 KB Output is correct
17 Correct 386 ms 15456 KB Output is correct
18 Correct 346 ms 15352 KB Output is correct
19 Correct 400 ms 15912 KB Output is correct
20 Correct 365 ms 16052 KB Output is correct
21 Correct 428 ms 15864 KB Output is correct