Submission #1263609

#TimeUsernameProblemLanguageResultExecution timeMemory
1263609NikoBaoticFurniture (JOI20_furniture)C++20
5 / 100
5096 ms40092 KiB
#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 k = n - 1; k >= 0; k--) { for (int j = m - 1; j >= 0; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...