oj.uz

Submission #660740

# Submission time Handle Problem Language Result Execution time Memory
660740 2022-11-23T06:21:37 Z USER Robots (APIO13_robots) C++14
60 / 100
 1500 ms 132696 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef pair <short, short> pr;
int k, n, m, a[501][501][45], nr;
char c[501][501];
int key[9][9];
bool STOP;
 
const int inf = 1000000000;
pr go[4][600][600];
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][key[l][r]] < a[aux.i][aux.j][key[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(short& i, short& 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;
}
 
int nxDir;
 
pr get(int dir, short i, short 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];
 
    if (nr == 1000000)
    {
        STOP = 1;
        return { 0, 0 };
    }
 
    nr++;
 
    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][key[l][r]] > val)
    {
        a[p.first][p.second][key[l][r]] = val;
        return 1;
    }
 
    return 0;
}
 
heap H;
 
void lee()
{
    int l, r, i, j, x, y;
 
    while (!H.empty())
    {
        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][key[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;
 
    int cnt = 0;
 
    for (int i = 0; i < k; i++)
        for (int j = i; j < k; j++)
            key[i][j] = cnt++;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            for (int l = 0; l < k; l++)
                for (int p = l; p < k; p++)
                    a[i][j][key[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++)
            {
                nr = 0;
                get(l, i, j);
 
                if (STOP)
                    return 0;
            }
 
    int aux;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (digit(c[i][j]))
            {
                aux = (c[i][j] - '0');
                update({ i, j }, 0, aux, aux);
                H.add({ i, j, unsigned(aux), unsigned(aux) });
                lee();
            }
 
    int q;
 
    for (int l = 2; l <= k; l++)
        for (int p = 0; p < k - l + 1; p++)
        {
            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][key[p][t]] + a[i][j][key[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][key[0][k - 1]]);
 
    if (mini == inf)
        cout << -1;
    else
        cout << mini;
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 0 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 0 ms 596 KB Output is correct
6 Correct 0 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 0 ms 596 KB Output is correct
6 Correct 0 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 539 ms 50604 KB Output is correct
12 Correct 28 ms 38984 KB Output is correct
13 Correct 151 ms 51436 KB Output is correct
14 Correct 1237 ms 50548 KB Output is correct
15 Correct 413 ms 50588 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 0 ms 596 KB Output is correct
6 Correct 0 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 539 ms 50604 KB Output is correct
12 Correct 28 ms 38984 KB Output is correct
13 Correct 151 ms 51436 KB Output is correct
14 Correct 1237 ms 50548 KB Output is correct
15 Correct 413 ms 50588 KB Output is correct
16 Correct 670 ms 132696 KB Output is correct
17 Execution timed out 1570 ms 132580 KB Time limit exceeded
18 Halted 0 ms 0 KB -