| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 469222 |
2021-08-31T07:30:06 Z |
urd05 |
Sandwich (JOI16_sandwich) |
C++17 |
|
8000 ms |
25212 KB |
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[400][401];
int dir[2][2][2]={{{0,1},{2,3}},{{0,3},{1,2}}}; //dir[N,Z][방향][그냥 저장]
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
typedef pair<int,int> P;
P lr[400][400][2];
typedef pair<P,int> Pi;
int cnt[400][400][2];
int ret[400][400][2];
int chk[4][2]={{0,0},{0,1},{1,1},{1,0}}; //방향,얘의 type
vector<Pi> adj[400][400][2];
bool valid(int x,int y) {
return x>=0&&x<n&&y>=0&&y<m;
}
const int INF=1e9;
int pcnt[400][400][2];
int main(void) {
scanf("%d %d\n",&n,&m);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
char c;
scanf("%c",&c);
if (c=='N') {
arr[i][j]=0;
}
else {
arr[i][j]=1;
}
}
scanf("\n");
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int l=0;l<2;l++) {
for(int k=0;k<2;k++) {
Pi now=Pi(P(i,j),l);
int ind;
int x=now.first.first+dx[dir[arr[now.first.first][now.first.second]][now.second][k]];
int y=now.first.second+dy[dir[arr[now.first.first][now.first.second]][now.second][k]];
if (!valid(x,y)) {
continue;
}
ind=chk[dir[arr[now.first.first][now.first.second]][now.second][k]][arr[x][y]];
adj[i][j][l].push_back(Pi(P(x,y),ind));
}
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<2;k++) {
if (valid(i+dx[dir[arr[i][j]][k^1][0]],j+dy[dir[arr[i][j]][k^1][0]])) {
pcnt[i][j][k]++;
}
if (valid(i+dx[dir[arr[i][j]][k^1][1]],j+dy[dir[arr[i][j]][k^1][1]])) {
pcnt[i][j][k]++;
}
}
}
}
for(int r=0;r<n;r++) {
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<2;k++) {
lr[i][j][k]=P(0,m-1);
cnt[i][j][k]=pcnt[i][j][k];
}
}
}
queue<Pi> q;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j+=m-1) {
for(int k=0;k<2;k++) {
if (cnt[i][j][k]==0) {
q.push(Pi(P(i,j),k));
lr[i][j][k]=P(0,m-1);
if (i==r&&j==0) {
lr[i][j][k].first=1;
}
if (i==r&&j==m-1) {
lr[i][j][k].second=m-2;
}
}
}
if (m==1) {
break;
}
}
}
while (!q.empty()) {
Pi now=q.front();
q.pop();
for(int i=0;i<adj[now.first.first][now.first.second][now.second].size();i++) {
Pi nt=adj[now.first.first][now.first.second][now.second][i];
lr[nt.first.first][nt.first.second][nt.second].first=max(lr[nt.first.first][nt.first.second][nt.second].first,lr[now.first.first][now.first.second][now.second].first);
lr[nt.first.first][nt.first.second][nt.second].second=min(lr[nt.first.first][nt.first.second][nt.second].second,lr[now.first.first][now.first.second][now.second].second);
cnt[nt.first.first][nt.first.second][nt.second]--;
if (cnt[nt.first.first][nt.first.second][nt.second]==0) {
if (nt.first.first==r) {
if (lr[nt.first.first][nt.first.second][nt.second].first==nt.first.second) {
lr[nt.first.first][nt.first.second][nt.second].first++;
}
if (lr[nt.first.first][nt.first.second][nt.second].second==nt.first.second) {
lr[nt.first.first][nt.first.second][nt.second].second--;
}
}
q.push(nt);
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
//printf("(%d,%d)and(%d,%d) ",lr[i][j][0].first,lr[i][j][0].second,lr[i][j][1].first,lr[i][j][1].second);
for(int k=0;k<2;k++) {
if (cnt[i][j][k]!=0) {
ret[i][j][k]=INF;
continue;
}
ret[i][j][k]+=m-max(0,lr[i][j][k].second-lr[i][j][k].first+1);
}
}
//printf("\n");
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int val=min(ret[i][j][0],ret[i][j][1]);
printf("%d ",val>=INF?-1:val*2);
}
printf("\n");
}
}
Compilation message
sandwich.cpp: In function 'int main()':
sandwich.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0;i<adj[now.first.first][now.first.second][now.second].size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sandwich.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d %d\n",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%c",&c);
| ~~~~~^~~~~~~~~
sandwich.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("\n");
| ~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9588 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 7 |
Correct |
21 ms |
9832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
9772 KB |
Output is correct |
| 9 |
Correct |
17 ms |
9676 KB |
Output is correct |
| 10 |
Correct |
23 ms |
9856 KB |
Output is correct |
| 11 |
Correct |
19 ms |
9864 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9572 KB |
Output is correct |
| 13 |
Correct |
20 ms |
9864 KB |
Output is correct |
| 14 |
Correct |
19 ms |
9804 KB |
Output is correct |
| 15 |
Correct |
21 ms |
9860 KB |
Output is correct |
| 16 |
Correct |
21 ms |
9868 KB |
Output is correct |
| 17 |
Correct |
21 ms |
9864 KB |
Output is correct |
| 18 |
Correct |
21 ms |
9804 KB |
Output is correct |
| 19 |
Correct |
21 ms |
9804 KB |
Output is correct |
| 20 |
Correct |
15 ms |
9860 KB |
Output is correct |
| 21 |
Correct |
14 ms |
9804 KB |
Output is correct |
| 22 |
Correct |
15 ms |
9856 KB |
Output is correct |
| 23 |
Correct |
17 ms |
9872 KB |
Output is correct |
| 24 |
Correct |
20 ms |
9860 KB |
Output is correct |
| 25 |
Correct |
20 ms |
9804 KB |
Output is correct |
| 26 |
Correct |
19 ms |
9860 KB |
Output is correct |
| 27 |
Correct |
18 ms |
9864 KB |
Output is correct |
| 28 |
Correct |
18 ms |
9860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 3 |
Correct |
8 ms |
9588 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9036 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9804 KB |
Output is correct |
| 7 |
Correct |
21 ms |
9832 KB |
Output is correct |
| 8 |
Correct |
21 ms |
9772 KB |
Output is correct |
| 9 |
Correct |
17 ms |
9676 KB |
Output is correct |
| 10 |
Correct |
23 ms |
9856 KB |
Output is correct |
| 11 |
Correct |
19 ms |
9864 KB |
Output is correct |
| 12 |
Correct |
11 ms |
9572 KB |
Output is correct |
| 13 |
Correct |
20 ms |
9864 KB |
Output is correct |
| 14 |
Correct |
19 ms |
9804 KB |
Output is correct |
| 15 |
Correct |
21 ms |
9860 KB |
Output is correct |
| 16 |
Correct |
21 ms |
9868 KB |
Output is correct |
| 17 |
Correct |
21 ms |
9864 KB |
Output is correct |
| 18 |
Correct |
21 ms |
9804 KB |
Output is correct |
| 19 |
Correct |
21 ms |
9804 KB |
Output is correct |
| 20 |
Correct |
15 ms |
9860 KB |
Output is correct |
| 21 |
Correct |
14 ms |
9804 KB |
Output is correct |
| 22 |
Correct |
15 ms |
9856 KB |
Output is correct |
| 23 |
Correct |
17 ms |
9872 KB |
Output is correct |
| 24 |
Correct |
20 ms |
9860 KB |
Output is correct |
| 25 |
Correct |
20 ms |
9804 KB |
Output is correct |
| 26 |
Correct |
19 ms |
9860 KB |
Output is correct |
| 27 |
Correct |
18 ms |
9864 KB |
Output is correct |
| 28 |
Correct |
18 ms |
9860 KB |
Output is correct |
| 29 |
Correct |
5 ms |
9084 KB |
Output is correct |
| 30 |
Correct |
41 ms |
13792 KB |
Output is correct |
| 31 |
Correct |
353 ms |
25212 KB |
Output is correct |
| 32 |
Correct |
363 ms |
25160 KB |
Output is correct |
| 33 |
Correct |
120 ms |
16432 KB |
Output is correct |
| 34 |
Execution timed out |
8018 ms |
24636 KB |
Time limit exceeded |
| 35 |
Halted |
0 ms |
0 KB |
- |
