oj.uz

답안 #660684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660684 2022-11-22T19:17:29 Z USER 로봇 (APIO13_robots) C++14
60 / 100
 1247 ms 163840 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;

typedef pair <int, int> pr;
int k, n, m, a[501][501][9][9], nr;
char c[501][501];

const int inf = 1000000000;
pr go[4][501][501];
int poz[501][501][9][9] = { 0 };

class heap {
    
private:

    int sz;
    
    struct nod {
        int i, j;
        unsigned l, r;

        bool operator < (nod& aux)
        {
            return a[i][j][l][r] < a[aux.i][aux.j][aux.l][aux.l];
        }
    };

    nod* h;

    void up(int k)
    {
        while (k > 1)
        {
            int k2 = k / 2;

            if (h[k] < h[k2])
            {
                swap(poz[h[k].i][h[k].j][h[k].l][h[k].r], poz[h[k2].i][h[k2].j][h[k2].l][h[k2].r]);
                swap(h[k], h[k2]), k = k2;
            }
            else
                break;
        }
    }

    void down(int k)
    {
        while (2 * k <= sz)
        {
            int k2 = 2 * k;

            if (h[k2] < h[k])
            {
                swap(poz[h[k].i][h[k].j][h[k].l][h[k].r], poz[h[k2].i][h[k2].j][h[k2].l][h[k2].r]);
                swap(h[k], h[k2]), k = k2;
            }
            else
                break;
        }
    }

public:

    heap()
    {
        sz = 0;
        h = new nod[300001];
    }

    void add(nod x)
    {
        sz++;
        h[sz] = x;
        poz[x.i][x.j][x.l][x.r] = sz;
        up(sz);
    }

    void pop()
    {
        swap(h[1], h[sz]);
        swap(poz[h[1].i][h[1].j][h[1].l][h[1].r], poz[h[sz].i][h[sz].j][h[sz].l][h[sz].r]);
        poz[h[sz].i][h[sz].j][h[sz].l][h[sz].r] = 0;
        sz--;
        down(1);
    }

    void update(nod x)
    {
        if (!poz[x.i][x.j][x.l][x.r])
            add(x);
        else
        {
            up(poz[x.i][x.j][x.l][x.r]);
            down(poz[x.i][x.j][x.l][x.r]);
        }
    }

    nod top()
    {
        return h[1];
    }

    bool empty()
    {
        return sz == 0;
    }
};

void afis(pr aux)
{
    cout << aux.first << ' ' << aux.second << '\n';
}

// 0 - Up, 1 - Left, 2 - Down, 3 - Right

int d1[] = { -1, 0, 1, 0 };
int d2[] = { 0, 1, 0, -1 };

inline bool in(int& i, int& j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

inline void prev(int& dir)
{
    dir--;
    if (dir == -1)
        dir = 3;
}

inline void next(int& dir)
{
    dir++;
    if (dir == 4)
        dir = 0;
}

pr get(int dir, int i, int j)
{
    if (!in(i, j) || c[i][j] == 'x')
    {
        next(dir);
        next(dir);
        return { i + d1[dir], j + d2[dir] };
    }

    if (go[dir][i][j].first)
        return go[dir][i][j];

    nr++;

    int nxDir = dir;

    if (c[i][j] == 'A')
        prev(nxDir);
    else if (c[i][j] == 'C')
        next(nxDir);

    pr aux = get(nxDir, i + d1[nxDir], j + d2[nxDir]);
    go[dir][i][j] = aux;
    return aux;
}

inline bool digit(char& c)
{
    return c >= '0' && c <= '9';
}

bool update(pr p, int val, int& l, int& r)
{
    if (a[p.first][p.second][l][r] > val)
    {
        a[p.first][p.second][l][r] = val;
        return 1;
    }

    return 0;
}

heap H;

void lee()
{
    int l, r, i, j, x, y;

    while (!H.empty())
    {
        nr++;
        i = H.top().i;
        j = H.top().j;
        l = H.top().l;
        r = H.top().r;
        H.pop();

        for (int p = 0; p <= 3; p++)
        {
            x = go[p][i][j].first;
            y = go[p][i][j].second;

            if (update({ x, y }, a[i][j][l][r] + 1, l, r))
                H.update({ x, y, unsigned(l), unsigned(r)});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> k >> m >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            for (int l = 0; l < k; l++)
                for (int p = 0; p < k; p++)
                    a[i][j][l][p] = inf;

            cin >> c[i][j];
            if (digit(c[i][j]))
                c[i][j]--;
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int l = 0; l <= 3; l++)
                get(l, i, j);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (digit(c[i][j]))
            {
                int aux = (c[i][j] - '0');
                update({ i, j }, 0, aux, aux);
                H.add({ i, j, unsigned(aux), unsigned(aux) });
                lee();
            }

    for (int l = 2; l <= k; l++)
        for (int p = 0; p < k - l + 1; p++)
        {
            int q = p + l - 1;
            
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    for (int t = p; t < q; t++)
                        update({ i, j }, a[i][j][p][t] + a[i][j][t + 1][q], p, q);

                    H.add({ i, j, unsigned(p), unsigned(q)});
                }

            lee();
        }

    int mini = inf;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            mini = min(mini, a[i][j][0][k - 1]);

    if (mini == inf)
        cout << -1;
    else
        cout << mini;

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 552 ms 64936 KB Output is correct
12 Correct 32 ms 53244 KB Output is correct
13 Correct 152 ms 66044 KB Output is correct
14 Correct 1247 ms 64928 KB Output is correct
15 Correct 457 ms 64936 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 552 ms 64936 KB Output is correct
12 Correct 32 ms 53244 KB Output is correct
13 Correct 152 ms 66044 KB Output is correct
14 Correct 1247 ms 64928 KB Output is correct
15 Correct 457 ms 64936 KB Output is correct
16 Runtime error 83 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -