oj.uz

Submission #489690

# Submission time Handle Problem Language Result Execution time Memory
489690 2021-11-24T01:15:43 Z 8e7 Virus Experiment (JOI19_virus) C++17
100 / 100
 1006 ms 84776 KB 
//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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 272 ms 18728 KB Output is correct
3 Correct 326 ms 18740 KB Output is correct
4 Correct 471 ms 18744 KB Output is correct
5 Correct 233 ms 18724 KB Output is correct
6 Correct 3 ms 6604 KB Output is correct
7 Correct 358 ms 19808 KB Output is correct
8 Correct 89 ms 11204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct
3 Correct 7 ms 1444 KB Output is correct
4 Correct 2 ms 1356 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 10 ms 2000 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 9 ms 1740 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 1356 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 2 ms 844 KB Output is correct
13 Correct 8 ms 1752 KB Output is correct
14 Correct 10 ms 1752 KB Output is correct
15 Correct 9 ms 1868 KB Output is correct
16 Correct 7 ms 1740 KB Output is correct
17 Correct 4 ms 1228 KB Output is correct
18 Correct 2 ms 716 KB Output is correct
19 Correct 7 ms 1740 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 272 ms 18728 KB Output is correct
3 Correct 326 ms 18740 KB Output is correct
4 Correct 471 ms 18744 KB Output is correct
5 Correct 233 ms 18724 KB Output is correct
6 Correct 3 ms 6604 KB Output is correct
7 Correct 358 ms 19808 KB Output is correct
8 Correct 89 ms 11204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 1356 KB Output is correct
11 Correct 7 ms 1444 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 10 ms 2000 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 9 ms 1740 KB Output is correct
17 Correct 2 ms 716 KB Output is correct
18 Correct 2 ms 1356 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 2 ms 844 KB Output is correct
21 Correct 8 ms 1752 KB Output is correct
22 Correct 10 ms 1752 KB Output is correct
23 Correct 9 ms 1868 KB Output is correct
24 Correct 7 ms 1740 KB Output is correct
25 Correct 4 ms 1228 KB Output is correct
26 Correct 2 ms 716 KB Output is correct
27 Correct 7 ms 1740 KB Output is correct
28 Correct 1006 ms 84744 KB Output is correct
29 Correct 756 ms 84776 KB Output is correct
30 Correct 542 ms 36504 KB Output is correct
31 Correct 608 ms 21116 KB Output is correct
32 Correct 667 ms 21280 KB Output is correct
33 Correct 381 ms 18912 KB Output is correct
34 Correct 791 ms 43004 KB Output is correct
35 Correct 489 ms 37748 KB Output is correct
36 Correct 507 ms 18760 KB Output is correct
37 Correct 765 ms 35248 KB Output is correct
38 Correct 606 ms 81820 KB Output is correct
39 Correct 319 ms 19684 KB Output is correct
40 Correct 386 ms 19652 KB Output is correct
41 Correct 254 ms 19212 KB Output is correct
42 Correct 707 ms 46652 KB Output is correct
43 Correct 710 ms 24096 KB Output is correct
44 Correct 94 ms 11204 KB Output is correct