Submission #286370

#	Time	Username	Problem	Language	Result	Execution time	Memory
286370		Alexa2001	Sandwich (JOI16_sandwich)	C++17	35 / 100	8041 ms	22936 KiB

sandwich

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;
const int Nmax = 404;

int cells, n, m, nr;
bool bad;

char a[Nmax][Nmax];
int ans[Nmax][Nmax];
int Upper[Nmax][Nmax], Lower[Nmax][Nmax];

vector<pair<pair<int,int>, int>> v;

void add_upper(int x, int y);


void add_lower(int x, int y)
{
    if(Lower[x][y] == 1) bad = 1;
    if(Lower[x][y]) return;
    Lower[x][y] = 1;
    v.push_back({{x, y}, 0});

    ++cells;

    if(a[x][y] == 'N') /// adaug dreapta
    {
        if(a[x][y+1] == 'N')
            add_lower(x, y+1);
        else if(a[x][y+1] == 'Z')
            add_upper(x, y+1);

        if(x - 1 >= 1)
            add_lower(x-1, y);
    }
    else
    {
        if(a[x][y-1] == 'N')
            add_upper(x, y-1);
        else if(a[x][y-1] == 'Z')
            add_lower(x, y-1);

        if(x - 1 >= 1)
            add_lower(x-1, y);
    }

    Lower[x][y] = 2;
}

void add_upper(int x, int y)
{
    if(Upper[x][y] == 1) bad = 1;
    if(Upper[x][y]) return;
    Upper[x][y] = 1;
    v.push_back({{x, y}, 1});

    ++cells;

    if(a[x][y] == 'N') /// adaug dreapta
    {
        if(a[x][y-1] == 'N')
            add_upper(x, y-1);
        else if(a[x][y-1] == 'Z')
            add_lower(x, y-1);

        if(x + 1 <= n)
            add_upper(x+1, y);
    }
    else
    {
        if(a[x][y+1] == 'N')
            add_lower(x, y+1);
        else if(a[x][y+1] == 'Z')
            add_upper(x, y+1);

        if(x + 1 <= n)
            add_upper(x+1, y);
    }

    Upper[x][y] = 2;
}

void solve1(int c)
{
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            Lower[i][j] = Upper[i][j] = 0;

    cells = 0;
    bad = 0;

    for(i=1; i<=n; ++i)
    {
        ++nr;
        add_lower(i, c);
        if(!bad) ans[i][c] = min(ans[i][c], cells);

        for(auto it : v)
            if(it.second == 0) Lower[it.first.first][it.first.second] = -1;
                else Upper[it.first.first][it.first.second] = -1;

        v.clear();
    }
}


void solve2(int c)
{
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            Lower[i][j] = Upper[i][j] = 0;

    cells = 0;
    bad = 0;

    for(i=n; i; --i)
    {
        ++nr;
        add_upper(i, c);
        if(!bad) ans[i][c] = min(ans[i][c], cells);

        for(auto it : v)
            if(it.second == 0) Lower[it.first.first][it.first.second] = -1;
                else Upper[it.first.first][it.first.second] = -1;

        v.clear();
    }
}


int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> m;

    int i, j;
    for(i=1; i<=n; ++i) cin >> (a[i] + 1);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            ans[i][j] = inf;

    for(i=1; i<=m; ++i)
        solve1(i);

    for(i=1; i<=m; ++i)
        solve2(i);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            cout << (ans[i][j] == inf ? -1 : 2 * ans[i][j]) << " \n"[j==m];

    return 0;
}

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