Submission #1266079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266079		Bahamin	Furniture (JOI20_furniture)	C++20	100 / 100	169 ms	14280 KiB

furniture

#include "bits/stdc++.h"

using namespace std;

#define all(a) (a).begin(), (a).end()
#define ll long long 
const int MAX_N = 1e3 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LOG = 30;

int in[MAX_N][MAX_N];
int out[MAX_N][MAX_N];
int have[MAX_N][MAX_N];
int cnt[MAX_N << 2];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;

bool add(int x, int y)
{
    if (cnt[x + y] == have[x][y]) return false;
    if (have[x][y])
    {   
        vector<pair<int, int>> qu;
        qu.push_back(make_pair(x, y));
        while (qu.size())
        {
            auto x1 = qu.back();
            qu.pop_back();
            have[x1.first][x1.second] = false;
            cnt[x1.first + x1.second]--;
            for (int i = 0; i < 2; i++)
            {
                int xx = x1.first + dx[i];
                int yy = x1.second + dy[i];
                if (have[xx][yy])
                {
                    in[xx][yy]--;
                    if (in[xx][yy] == 0) qu.push_back({xx, yy});
                }
            }
        }
        qu.push_back(make_pair(x, y));
        cnt[x + y]++;
        while (qu.size())
        {
            auto x1 = qu.back();
            qu.pop_back();
            have[x1.first][x1.second] = false;
            cnt[x1.first + x1.second]--;
            for (int i = 2; i < 4; i++)
            {
                int xx = x1.first + dx[i];
                int yy = x1.second + dy[i];
                if (have[xx][yy])
                {
                    out[xx][yy]--;
                    if (out[xx][yy] == 0) qu.push_back({xx, yy});
                }
            }
        }
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        have[i][j] = 1;
        cnt[i + j]++;
        in[i][j] = (i ? 1 : 0) + (j ? 1 : 0);
        out[i][j] = (i < n - 1 ? 1 : 0) + (j < m - 1 ? 1 : 0);
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        int c;
        cin >> c;
        if (c) add(i, j);
    }
    int  q;
    cin >> q;
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        if (add(x - 1, y - 1)) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
}

int main()
{
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

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