Submission #779814

#	Time	Username	Problem	Language	Result	Execution time	Memory
779814		raysh07	Furniture (JOI20_furniture)	C++17	100 / 100	206 ms	13012 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, m; 
const int N = 1005;
bool a[N][N], ok[N][N];
int cnt[2 * N];

void upd(int x, int y){
	if (!ok[x][y]) return;

	cnt[x + y]--;
	ok[x][y] = false;

	if (!ok[x - 1][y + 1]) upd(x - 1, y), upd(x, y + 1);
	if (!ok[x + 1][y - 1]) upd(x, y - 1), upd(x + 1, y);
}

void Solve()
{
	cin >> n >> m;

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cnt[i + j]++;
			ok[i][j] = true;
		}
	}

	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			int x; cin >> x;

			if (x) upd(i, j);
		}
	}

	int q; cin >> q;

	while(q--){
		int x, y; cin >> x >> y;

		if (!ok[x][y]) cout << 1 << "\n";
		else if (cnt[x + y] == 1) cout << 0 << "\n";
		else {
			cout << 1 << "\n";
			upd(x, y);
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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