Submission #924708

#	Time	Username	Problem	Language	Result	Execution time	Memory
924708		boris_mihov	Furniture (JOI20_furniture)	C++17	0 / 100	2 ms	6748 KiB

furniture

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
 
typedef long long llong;
const int MAXN = 1000 + 10;
const int INF  = 1e9;
 
int n, m, q;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int e[MAXN][MAXN];
int cntWithB[2 * MAXN];

bool empty[MAXN][MAXN];
std::vector <std::pair <int,int>> deltaB = {{1, 0}, {0, 1}};
std::vector <std::pair <int,int>> deltaE = {{-1, 0}, {0, -1}};

bool inside(int row, int col)
{
    return (row >= 1 && row <= n && col >= 1 && col <= m);
}

bool checkCell(int row, int col, std::vector <std::pair <int,int>> &delta, int d[][MAXN])
{
    int cnt = 0;
    for (const auto &[dx, dy] : delta)
    {
        if (inside(row - dx, col - dy) && d[row - dx][col - dy] == d[row][col] - 1 && !empty[row - dx][row - dy])
        {
            cnt++;
        }
    }

    return cnt > 0;
}

void runBFS(int row, int col, std::vector <std::pair <int,int>> &delta, int d[][MAXN])
{
    std::vector <std::pair <int,int>> toErase;
    std::queue <std::pair <int,int>> q;
    toErase.push_back({row, col});
    empty[row][col] = true;
    q.push({row, col});

    // std::cout << "runBFS: " << row << ' ' << col << '\n';
    while (q.size())
    {
        auto [currR, currC] = q.front();
        q.pop();
        
        for (const auto &[dx, dy] : delta)
        {
            if (!inside(currR + dx, currC + dy) || empty[currR + dx][currC + dy] || d[currR + dx][currC + dy] != d[currR][currC] + 1 || !checkCell(currR + dx, currC + dy, delta, d))
            {
                continue;
            }

            empty[currR + dx][currC + dy] = true;
            toErase.push_back({currR + dx, currC + dy});
            q.push({currR + dx, currC + dy});
        }
    }

    for (const auto &[x, y] : toErase)
    {
        if (!empty[x][y])
        {
            cntWithB[b[x][y]]--;
        }
        
        d[x][y] = MAXN - 1;
    }
}

bool destroy(int row, int col)
{
    // std::cout << "destroy: " << row << ' ' << col << ' ' << b[row][col] << ' ' << e[row][col] << '\n' << std::flush;
    if (b[row][col] + e[row][col] != n + m - 2)
    {
        return true;
    }

    if (cntWithB[b[row][col]] == 1)
    {
        return false;
    }

    runBFS(row, col, deltaB, b);
    runBFS(row, col, deltaE, e);
    return true;
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            b[i][j] = i - 1 + j - 1;
            e[i][j] = n - i + m - j;
            if (b[i][j] + e[i][j] == n + m - 2)
            {
                cntWithB[b[i][j]]++;
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            if (a[i][j] == 1)
            {
                destroy(i, j);
            }
        }
    }

    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     for (int j = 1 ; j <= m ; ++j)
    //     {
    //         std::cout << b[i][j] << ' ';
    //     }

    //     std::cout << '\n';
    // }

    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     for (int j = 1 ; j <= m ; ++j)
    //     {
    //         std::cout << e[i][j] << ' ';
    //     }

    //     std::cout << '\n';
    // }

    for (int i = 1 ; i <= q ; ++i)
    {
        int row, col;
        std::cin >> row >> col;
        std::cout << destroy(row, col) << '\n';
    }

    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     for (int j = 1 ; j <= m ; ++j)
    //     {
    //         std::cout << b[i][j] << ' ';
    //     }

    //     std::cout << '\n';
    // }

    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     for (int j = 1 ; j <= m ; ++j)
    //     {
    //         std::cout << e[i][j] << ' ';
    //     }

    //     std::cout << '\n';
    // }
}
 
void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            std::cin >> a[i][j];
        }
    }

    std::cin >> q;
}
 
void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}
 
int main()
{
    fastIOI();
    input();
    solve();
 
    return 0;
}

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