Submission #489690

#	Time	Username	Problem	Language	Result	Execution time	Memory
489690		8e7	Virus Experiment (JOI19_virus)	C++17	100 / 100	1006 ms	84776 KiB

virus

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <random>
#include <chrono>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 805
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
bool poss[maxn][maxn][16];
bool col[maxn][maxn];
int ans[maxn][maxn];
int u[maxn][maxn], ds[100005], dt[100005];
int ord[maxn*maxn], rev[maxn*maxn];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // NESW
int r, c;
inline bool in(int x, int y){return x >= 0 && x < r && y >= 0 && y < c;}
inline int conv(int x, int y){return x * c + y;};
bool con(int x, int y) {
	int mask = 0;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (in(dx, dy)) mask += col[dx][dy] ? (1<<i) : 0;
	}
	return poss[x][y][mask];
}
int pnt = 0;
vector<pii> found;
bool dfs(int x, int y, int st) {
	if (rev[conv(x, y)] < st) return 0;
	col[x][y] = 1;
	found.push_back({x, y});
	pnt++;
	bool ret = 1;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (!in(dx, dy)) continue;
		if (con(dx, dy) && !col[dx][dy]) {
			ret &= dfs(dx, dy, st);
			if (!ret) return 0;
		}
	}
	return 1;
}
int main() {
	io
	int m;
	cin >> m >> r >> c;
	string D;
	cin >> D;
	for (int i = 0;i < m;i++) ds[i] = (D[i] == 'N' ? 0 : (D[i] == 'E' ? 1 : (D[i] == 'S' ? 2 : 3)));
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) cin >> u[i][j];
	}
	for (int ti = 0;ti < 16;ti++) {
		int ma = 0, cur = 0, tot = 0, pref = 0, suf = 0;
		for (int i = 0;i < m;i++) {
			if (ti & (1<<ds[i])) {
				dt[i] = 1;
			} else {
				ma = max(ma, cur);
				cur = 0;
				dt[i] = 0;
			}
			cur += dt[i];
			tot += dt[i];
		}
		if (tot == m) {
			ma = 1<<30;	
		} else {
			for (int i = 0;i < m;i++) {
				if (!dt[i]) {
					pref = i;
					break;
				}
			}
			for (int i = m - 1;i >= 0;i--) {
				if (!dt[i]) {
					suf = m - 1 - i;
					break;
				}
			}
			ma = max(ma, pref + suf);
		}
		//debug(ma);
		for (int i = 0;i < r;i++) {
			for (int j = 0;j < c;j++) {
				poss[i][j][ti] = u[i][j] <= ma;
				if (u[i][j] == 0) poss[i][j][ti] = 0;
			}
		}
	}
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) ord[i*c+j] = i*c+j;
	}
	shuffle(ord, ord + r*c, mt);
	for (int i = 0;i < r*c;i++) rev[ord[i]] = i;
	int out = 1<<30, outn = 0;
	for (int ind = 0;ind < r * c;ind++) {
		int i = ord[ind]/c, j = ord[ind] % c;
		if (u[i][j]) {
			pnt = 0;
			for (auto p:found) col[p.ff][p.ss] = 0;
			found.clear();
			if (dfs(i, j, ind)) {
				if (pnt < out) {
					out = pnt;
					outn = pnt;
				} else if (pnt == out) outn+=pnt;
			}
			
		}
	}
	cout << out << "\n" << outn << "\n";
}
/*
 
7 3 4
EEEWWWE
1 1 0 1
1 0 1 3
1 1 1 1
*/

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80