Submission #294804

#	Time	Username	Problem	Language	Result	Execution time	Memory
294804		muhammad_hokimiyon	Furniture (JOI20_furniture)	C++14	100 / 100	384 ms	12280 KiB

furniture

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int N = 1e3 + 7;
const int M = 21;
const ll mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m,q;
int d[N + N];
int a[N][N];

int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};

int solve( int x , int y )
{
    if( a[x][y] )return 1;
    if( d[x + y] == 1 )return 0;
    queue < pair < int , int > > q;
    q.push({x , y});
    a[x][y] = 1;
    d[x + y] -= 1;
    while( !q.empty() ){
        auto f = q.front();
        q.pop();
        for( int i = 0; i < 4; i++ ){
            int nx = f.fi + dx[i];
            int ny = f.se + dy[i];
            if( nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] )continue;
            if( (a[nx + 1][ny] && a[nx][ny + 1] && nx + ny < n + m) || (a[nx - 1][ny] && a[nx][ny - 1] && nx + ny > 2) ){
                q.push({nx , ny});
                a[nx][ny] = 1;
                d[nx + ny] -= 1;
            }
        }
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    cin >> n >> m;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            cin >> a[i][j];
        }
    }
    vector < pair < int , int > > pref;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= m; j++ ){
            d[i + j] += 1;
            if( a[i][j] )pref.push_back({i , j});
            a[i][j] = 0;
        }
    }
    for( int i = 1; i <= 1000; i++ )a[0][i] = a[i][0] = a[i][m + 1] = a[n + 1][i] = 1;
    for( auto x : pref ){
        solve( x.fi , x.se );
    }
    cin >> q;
    while( q-- ){
        int x,y;
        cin >> x >> y;
        cout << solve( x , y ) << "\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95