Submission #1263610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263610		NikoBaotic	Furniture (JOI20_furniture)	C++20	100 / 100	1549 ms	106168 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 dis2[N][N];
int cnt2[N * N];
int ca2[N][N];

int ans[N * N];

int dfs(int x, int y) {
	if (x >= n or y >= m) { dis[x][y] = 1e9; return 1e9; }
	if (c[x][y]) { dis[x][y] = 1e9; 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];
}

int dfs2(int x, int y) {
	if (x >= n or y >= m or x == -1 or y == -1) return 1e9;
	if (c[x][y]) { dis2[x][y] = 1e9; return 1e9; }
	if (ca2[x][y] != -1) return dis2[x][y];

	dis2[x][y] = min(dis2[x][y], min(dfs2(x - 1, y) + 1, dfs2(x, y - 1) + 1));
	ca2[x][y] = 0;

	return dis2[x][y];
}

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

	dis[x][y] = min((int)1e9, min(dis[x + 1][y] + 1, dis[x][y + 1] + 1));
	dis2[x][y] = 1e9;

	if (x != 0) dis2[x][y] = min(dis2[x - 1][y] + 1, dis2[x][y]);
	if (y != 0) dis2[x][y] = min(dis2[x][y - 1] + 1, dis2[x][y]);
	
	if (bl[x][y] or c[x][y]) { dis[x][y] = 1e9; dis2[x][y] = 1e9; }

	if (x == 0 and y == 0) dis2[x][y] = 0;
	if (x == n - 1 and y == m - 1) dis[x][y] = 0;

	if (dis[x][y] == 1e9 or dis2[x][y] == 1e9) {
		dis[x][y] = 1e9;
		dis2[x][y] = 1e9;
	}

	if (bef < 1e9) cnt[bef]--; 
	if (dis[x][y] < 1e9) cnt[dis[x][y]]++;

	if (bef2 < 1e9) cnt2[bef2]--; 
	if (dis2[x][y] < 1e9) cnt2[dis2[x][y]]++;

	if (bef != dis[x][y] or bef2 != dis2[x][y]) {
		//cout << "CHANGE AT " << x << " " << y << endl;
		//cout << "FROM " << bef << " " << dis[x][y] << " FROM2 " << bef2 << " " << dis2[x][y] << endl;
		update(x - 1, y);
		update(x, y - 1);
		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;
			dis2[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;
	
	memset(ca2, -1, sizeof ca2);
	
	ca2[0][0] = 1;
	dis2[0][0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dfs(i, j);
			dfs2(i, j);
		}
	}
	//dfs(0, 0);
	//dfs2(n - 1, m - 1);

	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 k = 0; k < n; k++) {
		for (int j = 0; j < m; j++) {
			update(k, j);
		}
	}

	for (int i = 0; i < n * m; i++) {
		cnt[i] = 0;
		cnt2[i] = 0;
	}

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

	/*
	cout << "START" << endl;
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					cout << (dis2[k][j] == 1e9 ? -1 : dis2[k][j]) << " ";
				}
				cout << endl;
			}
			cout << endl;*/

	for (int i = l + 1; i < q; i++) {
		int x = qu[i].F - 1;
		int y = qu[i].S - 1;
		
		/*
		for (int k = 0; k < n * m; k++) {
			cnt[k] = 0;
			cnt2[k] = 0;
		}

			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
			if (dis[k][j] < 1e9) cnt[dis[k][j]]++;
			if (dis2[k][j] < 1e9) cnt2[dis2[k][j]]++;
				}
			}*/
		/*
		cout << "DIS " << endl;
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					cout << (dis[k][j] == 1e9 ? -1 : dis[k][j]) << " ";
				}
				cout << endl;
			}
			cout << endl;
		cout << "DIS2 " << endl;
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					cout << (dis2[k][j] == 1e9 ? -1 : dis2[k][j]) << " ";
				}
				cout << endl;
			}
			cout << endl;*/


		if ((dis[x][y] < 1e9 and cnt[dis[x][y]] <= 1) or (dis2[x][y] < 1e9 and cnt2[dis2[x][y]] <= 1)) {
			//cout << "POS " << x << " " << y << endl;
			//if (dis2[x][y] < 1e9) cout << "CANT " << cnt2[dis2[x][y]] << " " << dis2[x][y] << " 2" << endl;
			//if (dis[x][y] < 1e9) cout << "CANT " << cnt[dis2[x][y]] << " " << dis[x][y] << " 1" << endl;
			ans[i] = 0;
		} else {
			/*
			if (dis[x][y] < 1e9) {
				cnt[dis[x][y]]--;
			}

			if (dis2[x][y] < 1e9) {
				cnt2[dis2[x][y]]--;
			}*/

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

			//cout << "DONE" << endl;
			
			/*
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					cout << (dis2[k][j] == 1e9 ? -1 : dis2[k][j]) << " ";
				}
				cout << endl;
			}
			cout << endl;

			cout << "DONE " << x << " " << y << endl;
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					update(k, j);
				}
			}

			for (int k = n - 1; k >= 0; k--) {
				for (int j = m - 1; j >= 0; j--) {
					update(k, j);
				}
			}
			for (int k = 0; k < n; k++) {
				for (int j = 0; j < m; j++) {
					cout << (dis2[k][j] == 1e9 ? -1 : dis2[k][j]) << " ";
				}
				cout << endl;
			}
			cout << endl;

			cout << "END" << endl;*/

			ans[i] = 1;
		}
	}

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

	return 0;
}

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