Submission #1263574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263574		NikoBaotic	Furniture (JOI20_furniture)	C++20	0 / 100	7 ms	5700 KiB

furniture

#include "bits/stdc++.h"

using namespace std;

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

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 1e3 + 10;

int n, m, q;
int t[N][N];
int c[N][N];
pii qu[N * N];

int ca[N][N];
int dis[N][N];
int cnt[N * N];
bool bl[N][N];

int ans[N * N];

int dfs(int x, int y) {
	if (x >= n or y >= m) return 1e9;
	if (c[x][y]) return 1e9;
	if (ca[x][y] != -1) return dis[x][y];

	dis[x][y] = min(dis[x][y], min(dfs(x + 1, y) + 1, dfs(x, y + 1) + 1));
	ca[x][y] = 0;

	return dis[x][y];
}

void update(int x, int y) {
	if (x == -1 or y == -1) return;
	
	int bef = dis[x][y];

	dis[x][y] = min((int)1e9, min(dis[x + 1][y] + 1, dis[x][y + 1] + 1));
	if (bl[x][y] or c[x][y]) dis[x][y] = 1e9;
	
	if (bef < 1e9) cnt[bef]--;
	if (dis[x][y] < 1e9) cnt[dis[x][y]]++;

	if (bef != dis[x][y]) {
		update(x - 1, y);
		update(x , y - 1);
	}
}

bool can(int k) {
	if (k == q) return 0;

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			c[i][j] = t[i][j];
			dis[i][j] = 1e9;
			bl[i][j] = t[i][j];
		}
	}

	for (int i = 0; i <= k; i++) {
		c[qu[i].F - 1][qu[i].S - 1] = 1;
		bl[qu[i].F - 1][qu[i].S - 1] = 1;
	}

	memset(ca, -1, sizeof ca);

	ca[n - 1][m -1] = 1;
	dis[n - 1][m -1] = 0;

	dfs(0, 0);

	return dis[0][0] < 1e9;
}

int main() {
	FIO;
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> t[i][j];
		}
	}

	cin >> q;

	for (int i = 0; i < q; i++) {
		cin >> qu[i].F >> qu[i].S;
	}

	int l = 0;
	int r = q;

	while (l < r) {
		int mid = (l + r) / 2;

		if (can(mid)) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}

	for (int i = 0; i < l; i++) {
		ans[i] = 1;
	}

	can(l - 1);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dis[i][j] < 1e9) cnt[dis[i][j]]++;
		}
	}

	for (int i = l + 1; i < q; i++) {
		int x = qu[i].F - 1;
		int y = qu[i].S - 1;

		if (dis[x][y] < 1e9 and cnt[dis[x][y]] <= 1) {
			ans[i] = 0;
		} else {
			if (dis[x][y] < 1e9) {
				cnt[dis[x][y]]--;
			}

			bl[x][y] = 1;
			update(x, y);

			ans[i] = 1;
		}
	}

	for (int i = 0; i < q; i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

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