# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
358522 | BartolM | Furniture (JOI20_furniture) | C++17 | 2 ms | 1132 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=1005;
int n, m, q;
int mat[N][N];
int dp[N][N], cnt[N];
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
queue <pii> Q;
int ok(int x, int y) {
if (x<=0 || y<=0 || x>n || y>m) return 0;
if (!dp[x][y]) return 0;
return (!dp[x-1][y] && !dp[x][y-1]) || (!dp[x+1][y], !dp[x][y+1]);
}
void bfs(int x, int y) {
Q.push(mp(x, y));
while (!Q.empty()) {
pii pp=Q.front();
Q.pop();
for (int i=0; i<4; ++i) {
int nx=pp.X+dx[i], ny=pp.Y+dy[i];
if (!ok(nx, ny)) continue;
Q.push(mp(nx, ny));
dp[nx][ny]=0;
cnt[nx+ny]--;
}
}
}
void ispis() {
printf("-----------------------\n");
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
printf("%d ", dp[i][j]);
}
printf("\n");
}
printf("----------------------------\n");
}
void solve() {
dp[0][1]=1;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j]=(dp[i-1][j] || dp[i][j-1]) && mat[i][j];
}
}
dp[n+1][m]=1;
for (int i=n; i>=1; --i) {
for (int j=m; j>=1; --j) {
dp[i][j]&=dp[i+1][j] || dp[i][j+1];
cnt[i+j]+=dp[i][j];
}
}
while (q--) {
int x, y;
scanf("%d %d", &x, &y);
// ispis();
if (!dp[x][y]) {
printf("1\n");
continue;
}
cnt[x+y]--;
if (!cnt[x+y]) {
cnt[x+y]++;
printf("0\n");
continue;
}
printf("1\n");
dp[x][y]=0; mat[x][y]=0;
bfs(x, y);
}
}
void load() {
scanf("%d %d", &n, &m);
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
scanf("%d", &mat[i][j]);
mat[i][j]^=1;
}
}
scanf("%d", &q);
}
int main() {
load();
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |