Submission #138412

#	Time	Username	Problem	Language	Result	Execution time	Memory
138412		qkxwsm	Virus Experiment (JOI19_virus)	C++14	6 / 100	2070 ms	4252 KiB

virus

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 813
#define MAXD 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, D;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; //NWSE
int dir[MAXD];
int grid[MAXN][MAXN];
int st[17];
pii ans = {INF, 0};
bitset<MAXN> dead[MAXN];

void test(int x, int y)
{
	if (grid[x][y] == 0) return;
	FOR(i, 0, N)
	{
		FOR(j, 0, M)
		{
			dead[i][j] = false;
		}
	}
	dead[x][y] = true;
	int res = 0;
	queue<pii> q;
	q.push({x, y});
	// cerr << "KILL " << x << ' ' << y << endl;
	while(!q.empty())
	{
		res++;
		pii p = q.front(); q.pop();
		// cerr << "DEAD " << p.fi << ' ' << p.se << endl;
		FOR(k, 0, 4)
		{
			//try seeing if this guy is dead!
			int nx = p.fi + dx[k], ny = p.se + dy[k];
			if (grid[nx][ny] == 0 || dead[nx][ny]) continue;
			//find the guys who are dead!
			int dm = 0;
			FOR(m, 0, 4)
			{
				if (dead[nx + dx[m]][ny + dy[m]]) dm += (1 << m);
			}
			if (st[dm] >= grid[nx][ny])
			{
				// if (nx == 1 && ny == 4) cerr << dm << ' ' << st[dm] << endl;
				dead[nx][ny] = true;
				q.push({nx, ny});
			}
		}
	}
	// cerr << "result " << res << endl;
	if (res < ans.fi)
	{
		ans = {res, 1};
	}
	else if (res == ans.fi)
	{
		ans.se++;
	}
	return;
}
bool check(int t, int mask)
{
	int freq[4] = {0, 0, 0, 0};
	FOR(i, 0, t)
	{
		freq[dir[i]]++;
	}
	FOR(i, t, 2 * D)
	{
		//check if this guy is ok!
		bool ok = true;
		FOR(j, 0, 4)
		{
			if ((mask & (1 << j))) continue;
			if (freq[j])
			{
				ok = false;
				break;
			}
		}
		if (ok)
		{
			return true;
		}
		freq[dir[i]]++;
		freq[dir[i - t]]--;
	}
	return false;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> D >> N >> M;
	string temps; cin >> temps;
	FOR(i, 0, D)
	{
		if (temps[i] == 'N') dir[i] = 0;
		if (temps[i] == 'W') dir[i] = 1;
		if (temps[i] == 'S') dir[i] = 2;
		if (temps[i] == 'E') dir[i] = 3;
		dir[i + D] = dir[i];
	}
	N += 2; M += 2;
	FOR(i, 1, N - 1)
	{
		FOR(j, 1, M - 1)
		{
			cin >> grid[i][j]; //lol careful: bigger number means you're more resistant unless your # is 0
			ckmin(grid[i][j], D);
		}
	}
	//for each of the 16 masks, figure out the shortest time such that having this mask is fatal
	FOR(i, 0, (1 << 4))
	{
		//longest block that contains every single one of these symbols!
		int lo = 0, hi = D + 1;
		while(hi > lo)
		{
			int mid = (hi + lo + 1) >> 1;
			if (check(mid, i)) lo = mid;
			else hi = mid - 1;
		}
		st[i] = lo;
		// cerr << "st " << i << " = " << st[i] << endl;
	}
	FOR(i, 1, N - 1)
	{
		FOR(j, 1, M - 1)
		{
			test(i, j);
		}
	}
	cout << ans.fi << '\n' << ans.se << '\n';
	return 0;
}

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