Submission #241665

#	Time	Username	Problem	Language	Result	Execution time	Memory
241665		ChrisT	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	1184 ms	262148 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;
char grid[MN][MN]; int cnt[MN][MN];
inline int hsh (int a, int b, int c, int d) {return d | (c << 1) | (b << 14) | (a << 28);}
int main () {
	int n,m; set<int> st;
	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];st.insert(hsh(cnt[i][j]+cnt[i+1][j]+cnt[i+2][j],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') {
			st.insert(hsh(cnt[i][j]+cnt[i][j+1]+cnt[i][j+2],i,j,0));
		}
	}
	auto del1 = [&] (int x, int y) {
		auto it = st.find(hsh(cnt[x][y]+cnt[x][y+1]+cnt[x][y+2],x,y,0));
		if (it != st.end()) {
			st.erase(it);
			--cnt[x][y];--cnt[x][y+1];--cnt[x][y+2];
			if (cnt[x][y]) {
				it = st.find(hsh(2+cnt[x+1][y]+cnt[x+2][y],x,y,1));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(1+cnt[x+1][y]+cnt[x+2][y],x,y,1));
				}
			}
			if (cnt[x][y+1]) {
				it = st.find(hsh(cnt[x-1][y+1]+2+cnt[x+1][y+1],x-1,y+1,1));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(cnt[x-1][y+1]+1+cnt[x+1][y+1],x-1,y+1,1));
				}
			}
			if (cnt[x][y+2]) {
				it = st.find(hsh(cnt[x-2][y+2]+cnt[x-1][y+2]+2,x-2,y+2,1));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(cnt[x-2][y+2]+cnt[x-1][y+2]+1,x-2,y+2,1));
				}
			}
		}
	};
	auto del2 = [&] (int x, int y) {
		auto it = st.find(hsh(cnt[x][y]+cnt[x+1][y]+cnt[x+2][y],x,y,1));
		if (it != st.end()) {
			st.erase(it);
			--cnt[x][y]; --cnt[x+1][y]; --cnt[x+2][y];
			if (cnt[x][y]) {
				it = st.find(hsh(2+cnt[x][y+1]+cnt[x][y+2],x,y,0));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(1+cnt[x][y+1]+cnt[x][y+2],x,y,0));
				}
			}
			if (cnt[x+1][y]) {
				it = st.find(hsh(cnt[x+1][y-1]+2+cnt[x+1][y+1],x+1,y-1,0));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(cnt[x+1][y-1]+1+cnt[x+1][y+1],x+1,y-1,0));
				}
			}
			if (cnt[x+2][y]) {
				it = st.find(hsh(cnt[x+2][y-2]+cnt[x+2][y-1]+2,x+2,y-2,0));
				if (it != st.end()) {
					st.erase(it);
					st.insert(hsh(cnt[x+2][y-2]+cnt[x+2][y-1]+1,x+2,y-2,0));
				}
			}
		} 
	};
	int ret = 0;
	while (!st.empty()) {
		int cur = *st.begin(); st.erase(st.begin()); ++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;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:20: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:22: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