Submission #469222

#	Time	Username	Problem	Language	Result	Execution time	Memory
469222		urd05	Sandwich (JOI16_sandwich)	C++17	35 / 100	8018 ms	25212 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<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 (stderr)

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");
      |         ~~~~~^~~~~~

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