| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 491654 | patrikpavic2 | Sandwich (JOI16_sandwich) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <bitset>
#include <queue>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
const int N = 405;
int n, m;
char A[N][N];
int jos[N][N][2], bio[N][N][2];
queue < pair < pair < int, int >, int > > Q;
bitset < N * N > koji[N * N][2];
inline int kod(int i, int j){
return i * m + j;
}
void smanji(int i, int j, int k, int oi, int oj, int ok){
jos[i][j][k]--; koji[kod(i, j)][k] |= koji[kod(oi, oj)][ok];
if(!jos[i][j][k])
Q.push({{i, j}, k});
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
koji[kod(i, j)][0][kod(i, j)] = 1;
koji[kod(i, j)][1][kod(i, j)] = 1;
scanf(" %c", &A[i][j]);
if(A[i][j] == 'Z'){
jos[i][j][0] = (!!i) + (!!j); jos[i][j][1] = (!!(n - i - 1)) + (!!(m - j - 1));
}
else{
jos[i][j][0] = (!!i) + (!!(m - j - 1)); jos[i][j][1] = (!!(n - i - 1)) + (!!j);
}
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(!jos[i][j][0]) Q.push({{i, j}, 0});
if(!jos[i][j][1]) Q.push({{i, j}, 1});
}
}
for(;!Q.empty();Q.pop()){
int cx = Q.front().X.X, cy = Q.front().X.Y;
int sm = Q.front().Y;
// printf("%d %d %d\n", cx, cy, sm);
bio[cx][cy][sm] = 1;
if(A[cx][cy] == 'N' && sm == 0){
if(cy) smanji(cx, cy - 1, A[cx][cy - 1] == 'Z', cx, cy, sm);
if(cx + 1 < n) smanji(cx + 1, cy, 0, cx, cy, sm);
}
if(A[cx][cy] == 'N' && sm == 1){
if(cx) smanji(cx - 1, cy, 1, cx, cy, sm);
if(cy + 1 < m) smanji(cx, cy + 1, A[cx][cy + 1] == 'N', cx, cy, sm);
}
if(A[cx][cy] == 'Z' && sm == 0){
if(cx + 1 < n) smanji(cx + 1, cy, 0, cx, cy, sm);
if(cy + 1 < m) smanji(cx, cy + 1, A[cx][cy + 1] == 'N', cx, cy, sm);
}
if(A[cx][cy] == 'Z' && sm == 1){
if(cx) smanji(cx - 1, cy, 1, cx, cy, sm);
if(cy) smanji(cx, cy - 1, A[cx][cy - 1] == 'Z', cx, cy, sm);
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
int ans = N * N;
if(bio[i][j][0]) ans = min(ans, (int)koji[kod(i, j)][0].count());
if(bio[i][j][1]) ans = min(ans, (int)koji[kod(i, j)][1].count());
printf("%d ", ans == N * N ? -1 : 2 * ans);
}
printf("\n");
}
return 0;
}