Submission #294704

#	Time	Username	Problem	Language	Result	Execution time	Memory
294704		Alexa2001	Furniture (JOI20_furniture)	C++17	100 / 100	428 ms	16052 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95