Submission #294438

#	Time	Username	Problem	Language	Result	Execution time	Memory
294438		ChrisT	Furniture (JOI20_furniture)	C++17	100 / 100	466 ms	17920 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e3+5, MOD = 1e9 + 7, BASE = 143;
bool canL[MN][MN], canR[MN][MN];
int a[MN][MN], cnt[MN * 2];
int main () {
	int n,m;
	scanf ("%d %d",&n,&m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf ("%d",&a[i][j]);
			canL[i][j] = !a[i][j] && (i*j==1 || canL[i-1][j] || canL[i][j-1]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 1; j--) {
			canR[i][j] = !a[i][j] && ((i==n&&j==m)||canR[i+1][j]||canR[i][j+1]);
			cnt[i+j] += canR[i][j] && canL[i][j];
		}
	}
	function<void(int,int)> fixL = [&] (int x, int y) {
		if (x > n || y > m || !canL[x][y] || (canL[x][y] = canL[x-1][y] || canL[x][y-1])) return;
		cnt[x+y] -= canR[x][y];
		fixL(x+1,y); fixL(x,y+1);
	};
	function<void(int,int)> fixR = [&] (int x, int y) {
		if (x <= 0 || y <= 0 || !canR[x][y] || (canR[x][y] = canR[x+1][y] || canR[x][y+1])) return;
		cnt[x+y] -= canL[x][y];
		fixR(x-1,y); fixR(x,y-1);
	};
	int q; scanf ("%d",&q);
	while (q--) {
		int x,y;
		scanf ("%d %d",&x,&y);
		if (!(canL[x][y] && canR[x][y])) {printf ("1\n"); continue;}
		if (cnt[x+y] == 1) {printf ("0\n"); continue;}
		canL[x][y] = canR[x][y] = 0;
		--cnt[x+y];
		fixR(x-1,y); fixR(x,y-1);
		fixL(x+1,y); fixL(x,y+1);
		printf ("1\n");
	}
	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |  scanf ("%d %d",&n,&m);
      |  ~~~~~~^~~~~~~~~~~~~~~
furniture.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |    scanf ("%d",&a[i][j]);
      |    ~~~~~~^~~~~~~~~~~~~~~
furniture.cpp:31:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  int q; scanf ("%d",&q);
      |         ~~~~~~^~~~~~~~~
furniture.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf ("%d %d",&x,&y);
      |   ~~~~~~^~~~~~~~~~~~~~~

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