Submission #469224

#	Time	Username	Problem	Language	Result	Execution time	Memory
469224		urd05	Sandwich (JOI16_sandwich)	C++17	35 / 100	204 ms	262148 KiB

sandwich

#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<short,short> P;
P lr[400][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]++;
                }
            }
        }
    }
    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++) {
                for(int r=0;r<n;r++)
                lr[i][j][r][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));
                    if (j==0) {
                        lr[i][j][i][k].first=1;
                    }
                    if (j==m-1) {
                        lr[i][j][i][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];
            for(int r=0;r<n;r++) {
                lr[nt.first.first][nt.first.second][r][nt.second].first=max(lr[nt.first.first][nt.first.second][r][nt.second].first,lr[now.first.first][now.first.second][r][now.second].first);
                lr[nt.first.first][nt.first.second][r][nt.second].second=min(lr[nt.first.first][nt.first.second][r][nt.second].second,lr[now.first.first][now.first.second][r][now.second].second);
            }
            cnt[nt.first.first][nt.first.second][nt.second]--;
            if (cnt[nt.first.first][nt.first.second][nt.second]==0) {
                    if (lr[nt.first.first][nt.first.second][nt.first.first][nt.second].first==nt.first.second) {
                        lr[nt.first.first][nt.first.second][nt.first.first][nt.second].first++;
                    }
                    if (lr[nt.first.first][nt.first.second][nt.first.first][nt.second].second==nt.first.second) {
                        lr[nt.first.first][nt.first.second][nt.first.first][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;
                }
                for(int r=0;r<n;r++)
                ret[i][j][k]+=m-max(0,lr[i][j][r][k].second-lr[i][j][r][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 (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<short int, short int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         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");
      |         ~~~~~^~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 0 / 65