#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
1016 KB |
Output is correct |
| 2 |
Execution timed out |
2070 ms |
4252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
191 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
271 ms |
1644 KB |
Output is correct |
| 4 |
Correct |
211 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
275 ms |
1528 KB |
Output is correct |
| 6 |
Correct |
490 ms |
1656 KB |
Output is correct |
| 7 |
Correct |
3 ms |
376 KB |
Output is correct |
| 8 |
Correct |
265 ms |
1656 KB |
Output is correct |
| 9 |
Correct |
123 ms |
632 KB |
Output is correct |
| 10 |
Correct |
205 ms |
1528 KB |
Output is correct |
| 11 |
Correct |
23 ms |
504 KB |
Output is correct |
| 12 |
Correct |
365 ms |
504 KB |
Output is correct |
| 13 |
Correct |
386 ms |
1656 KB |
Output is correct |
| 14 |
Correct |
374 ms |
1564 KB |
Output is correct |
| 15 |
Correct |
383 ms |
1656 KB |
Output is correct |
| 16 |
Correct |
376 ms |
1528 KB |
Output is correct |
| 17 |
Correct |
146 ms |
1144 KB |
Output is correct |
| 18 |
Correct |
32 ms |
504 KB |
Output is correct |
| 19 |
Correct |
288 ms |
1692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
1016 KB |
Output is correct |
| 2 |
Execution timed out |
2070 ms |
4252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
