Submission #241664

#	Time	Username	Problem	Language	Result	Execution time	Memory
241664		ChrisT	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	1468 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;
char grid[MN][MN]; int cnt[MN][MN];
struct Thing {
	int val,i,j; bool dir;
	bool operator< (const Thing &o) const {return mp(val,mp(i,mp(j,dir))) < mp(o.val,mp(o.i,mp(o.j,o.dir)));}
};
int main () {
	int n,m; set<Thing> 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({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({cnt[i][j]+cnt[i][j+1]+cnt[i][j+2],i,j,0});
		}
	}
	auto del1 = [&] (int x, int y) {
		auto it = st.find({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({2+cnt[x+1][y]+cnt[x+2][y],x,y,1});
				if (it != st.end()) {
					st.erase(it);
					st.insert({1+cnt[x+1][y]+cnt[x+2][y],x,y,1});
				}
			}
			if (cnt[x][y+1]) {
				it = st.find({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({cnt[x-1][y+1]+1+cnt[x+1][y+1],x-1,y+1,1});
				}
			}
			if (cnt[x][y+2]) {
				it = st.find({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({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({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({2+cnt[x][y+1]+cnt[x][y+2],x,y,0});
				if (it != st.end()) {
					st.erase(it);
					st.insert({1+cnt[x][y+1]+cnt[x][y+2],x,y,0});
				}
			}
			if (cnt[x+1][y]) {
				it = st.find({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({cnt[x+1][y-1]+1+cnt[x+1][y+1],x+1,y-1,0});
				}
			}
			if (cnt[x+2][y]) {
				it = st.find({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({cnt[x+2][y-2]+cnt[x+2][y-1]+1,x+2,y-2,0});
				}
			}
		} 
	};
	int ret = 0;
	while (!st.empty()) {
		Thing cur = *st.begin(); st.erase(st.begin()); ++ret;
		int x = cur.i, y = cur.j;
		if (cur.dir) {
			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:23: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:25: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