제출 #241668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241668		ChrisT	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	711 ms	104444 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define mp make_pair
#define lc ind<<1
#define rc ind<<1|1
const int MN = 3e3+5, MOD = 1e9+7, BASE = 31, MASK = (1 << 13) - 1;
vector<int> cancer[7];
bitset<MN * 2 * MASK> done;
char grid[MN][MN]; int cnt[MN][MN];
inline int hsh (int a, int b, int c) {return c | (b << 1) | (a << 14);}
int main () {
	int n,m;
	scanf ("%d %d",&n,&m);
	for (int i = 1; i <= n; i++) {
		scanf ("%s",grid[i]+1);
		for (int j = 1; j <= m-2; j++) if (grid[i][j] == 'R' && grid[i][j+1] == 'G' && grid[i][j+2] == 'W') {
			cnt[i][j]=cnt[i][j+1]=cnt[i][j+2]=1;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n-2; i++) if (grid[i][j] == 'R' && grid[i+1][j] == 'G' && grid[i+2][j] == 'W') {
			++cnt[i][j];++cnt[i+1][j];++cnt[i+2][j];cancer[cnt[i][j]+cnt[i+1][j]+cnt[i+2][j]].push_back(hsh(i,j,1));
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m-2; j++) if (grid[i][j]=='R'&&grid[i][j+1]=='G'&&grid[i][j+2]=='W') {
			cancer[cnt[i][j]+cnt[i][j+1]+cnt[i][j+2]].push_back(hsh(i,j,0));
		}
	}
	auto del1 = [&] (int x, int y) {
		if (!done.test(hsh(x,y,0))) {
			done.set(hsh(x,y,0));
			--cnt[x][y];--cnt[x][y+1];--cnt[x][y+2];
			if (cnt[x][y]) {
				if (!done.test(hsh(x,y,1))) {
					cancer[1+cnt[x+1][y]+cnt[x+2][y]].push_back(hsh(x,y,1));
				}
			}
			if (cnt[x][y+1]) {
				if (!done.test(hsh(x-1,y+1,1))) {
					cancer[cnt[x-1][y+1]+1+cnt[x+1][y+1]].push_back(hsh(x-1,y+1,1));
				}
			}
			if (cnt[x][y+2]) {
				if (!done.test(hsh(x-2,y+2,1))) {
					cancer[cnt[x-2][y+2]+cnt[x-1][y+2]+1].push_back(hsh(x-2,y+2,1));
				}
			}
		}
	};
	auto del2 = [&] (int x, int y) {
		if (!done.test(hsh(x,y,1))) {
			done.set(hsh(x,y,1));
			--cnt[x][y]; --cnt[x+1][y]; --cnt[x+2][y];
			if (cnt[x][y]) {
				if (!done.test(hsh(x,y,0))) {
					cancer[1+cnt[x][y+1]+cnt[x][y+2]].push_back(hsh(x,y,0));
				}
			}
			if (cnt[x+1][y]) {
				if (!done.test(hsh(x+1,y-1,0))) {
					cancer[cnt[x+1][y-1]+1+cnt[x+1][y+1]].push_back(hsh(x+1,y-1,0));
				}
			}
			if (cnt[x+2][y]) {
				if (!done.test(hsh(x+2,y-2,0))) {
					cancer[cnt[x+2][y-2]+cnt[x+2][y-1]+1].push_back(hsh(x+2,y-2,0));
				}
			}
		} 
	};
	auto getmin = [&] () {
		for (int i = 0; i < 7; i++) if (!cancer[i].empty()) {
			int ret = cancer[i].back();
			cancer[i].pop_back();
			return ret;
		}
		return -1;
	};
	int ret = 0, cur;
	while (~(cur=getmin())) {
		if (done.test(cur)) continue;
		done.set(cur); ++ret;
		int x = (cur>>14)&MASK, y = (cur>>1)&MASK;
		if (cur&1) {
			if (cnt[x][y]==2) del1(x,y);
			if (cnt[x+1][y]==2) del1(x+1,y-1);
			if (cnt[x+2][y]==2) del1(x+2,y-2);
		} else {
			if (cnt[x][y] == 2) del2(x,y);
			if (cnt[x][y+1] == 2) del2(x-1,y+1);
			if (cnt[x][y+2] == 2) del2(x-2,y+2);
		}
	}
	printf("%d\n",ret);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&m);
  ~~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s",grid[i]+1);
   ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67