Submission #1255487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255487		Sam_arvandi	Furniture (JOI20_furniture)	C++20	100 / 100	384 ms	51460 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;;
typedef pair<int, int> pii;

#define FOR(i, j, n) for(int i = j; i<= n; i++)
#define ROF(i, n, j) for(int i = n; i>= j; i--)
#define pb push_back
#define S second
#define F first
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define print(i) cout << #i << ": " << i << endl
const int mn = 1000 + 5;

bool flag1[mn][mn], flag2[mn][mn];
set<pii> s[mn*2];


void f1(int x, int y)
{
        if (!flag1[x][y]) return;
        if (flag2[x][y]) s[x+y].erase({x, y});
        flag1[x][y] = 0;
        if (!flag1[x-1][y+1]) f1(x, y+1);
        if (!flag1[x+1][y-1]) f1(x+1, y);
        return;
}

void f2(int x, int y)
{
        if (!flag2[x][y]) return;
        if (flag1[x][y]) s[x+y].erase({x, y});
        flag2[x][y] = 0;
        if (!flag2[x-1][y+1]) f2(x-1, y);
        if (!flag2[x+1][y-1]) f2(x, y-1);
        return;
}

signed main()
{
        IOS;
        int n, m, u, v, x, y;
        cin >> n >> m;
        FOR(i, 1, n)
        {
                FOR(j, 1, m)
                {
                        flag1[i][j] = flag2[i][j] = 1;
                        s[i+j].insert({i, j});
                }
        }
        FOR(i, 1, n)
        {
                FOR(j, 1, m)
                {
                        cin >> u;
                        if (u == 0) continue;
                        f1(i, j);
                        f2(i, j);
                }
        }
        int q;
        cin >> q;
        while (q--)
        {
                cin >> x >> y;
                if (s[x+y].size() == 1 and flag1[x][y] and flag2[x][y])
                {
                        cout << 0 << "\n";
                        continue;
                }
                f1(x, y);
                f2(x, y);
                cout << 1 << "\n";
        }

        return 0;
}

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