oj.uz

답안 #660661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660661 2022-11-22T18:04:34 Z USER 로봇 (APIO13_robots) C++14
30 / 100
 1500 ms 37172 KB 
#include <bits/stdc++.h>
using namespace std;

class input {

private:

    FILE* fin;
    const int sz = 10000;
    char* buff, c;
    int p;
    const char stop = char(-51);

    char read()
    {
        if (p == sz)
        {
            fread(buff, 1, sz, fin);
            p = 0;
            return buff[p++];
        }
        else
            return buff[p++];
    }

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

public:

    input(const char* name)
    {
        c = '-';
        buff = new char[sz];
        p = 0;
        fin = fopen(name, "r");
        fread(buff, 1, sz, fin);
    }

    void close()
    {
        fclose(fin);
    }

    void open(const char* name)
    {
        c = '-';
        p = sz;
        fin = fopen(name, "r");
    }

    bool eof()
    {
        int i = p;

        while (true)
        {
            while (i < sz && (buff[i] == ' ' || buff[i] == '\n'))
                i++;

            if (i != sz)
            {
                if (buff[i] == stop)
                    return 1;
                return 0;
            }
            else
            {
                fread(buff, 1, sz, fin);
                p = 0;
                i = 0;
            }
        }
    }

    input& operator >> (int& n)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;
        int sng = 1;

        if (c == '-')
            sng = -1, c = read();

        while (digit(c))
            n = n * 10 + (c - '0'), c = read();

        n *= sng;

        return *this;
    }

    input& operator >> (long long& n)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;
        int sng = 1;

        if (c == '-')
            sng = -1, c = read();

        while (digit(c))
            n = n * 10 + (c - '0'), c = read();

        n *= sng;

        return *this;
    }

    input& operator >> (unsigned long long& n)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;
        int sng = 1;

        if (c == '-')
            sng = -1, c = read();

        while (digit(c))
            n = n * 10 + (c - '0'), c = read();

        n *= sng;

        return *this;
    }

    input& operator >> (char& ch)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        ch = c;

        return *this;
    }

    input& operator >> (string& n)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = "";

        while (c != ' ' && c != '\n' && c != '\0')
            n += c, c = read();

        return *this;
    }

    input& operator >> (double& n)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;

        while (digit(c))
            n = n * 10 + (c - '0'), c = read();

        if (c != '.')
            return *this;

        c = read();

        double p10 = 10;

        while (digit(c))
            n = n + double(c - '0') / p10, c = read(), p10 *= 10;

        return *this;
    }

    input& operator >> (char* s)
    {
        c = read();

        while (c == ' ' || c == '\n')
            c = read();

        while (c != ' ' && c != '\n')
            *s = c, s++, c = read();

        *s = '\0';

        return *this;
    }

    void getline(string& s)
    {
        s = "";

        c = read();

        while (c == ' ')
            c = read();

        while (c != '\n')
            s += c, c = read();
    }
};
class output {

private:
    FILE* fout;
    const int sz = 10000;
    char* buff;
    int p;

    void write(char ch)
    {
        if (p == sz)
        {
            fwrite(buff, 1, sz, fout);
            p = 0;
            buff[p++] = ch;
        }
        else
            buff[p++] = ch;
    }

public:

    output(const char* name)
    {
        buff = new char[sz];
        p = 0;
        fout = fopen(name, "w");
    }

    ~output()
    {
        fwrite(buff, 1, p, fout);
    }

    output& operator << (int n)
    {
        if (n < 0)
            write('-'), n *= -1;

        if (n == 0)
        {
            write(n + '0');
            return *this;
        }

        if (n / 10 != 0)
            *this << (n / 10);

        write(('0' + (n % 10)));

        return *this;
    }

    output& operator << (long long n)
    {
        if (n < 0)
        {
            write('-');
            n *= -1;
        }

        if (n < 10)
        {
            write(n + '0');
            return *this;
        }

        *this << (n / 10);
        write((n % 10) + '0');

        return *this;
    }

    output& operator << (unsigned long long n)
    {
        if (n < 0)
        {
            write('-');
            n *= -1;
        }

        if (n < 10)
        {
            write(n + '0');
            return *this;
        }

        *this << (n / 10);
        write((n % 10) + '0');

        return *this;
    }

    output& operator << (char c)
    {
        write(c);
        return *this;
    }

    void precision(double n, int x)
    {
        *this << int(n);

        if (!x)
            return;

        write('.');

        n -= int(n);
        n *= 10;

        for (int i = 1; i <= x; i++)
        {
            *this << int(n);
            n -= int(n);
            n *= 10;
        }
    }

    output& operator << (string n)
    {
        for (auto i : n)
            write(i);
        return *this;
    }
};

ifstream fin("number.in");
ofstream fout("number.out");

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];

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

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

priority_queue <nod> Q;

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;
}

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

    while (!Q.empty())
    {
        i = Q.top().i;
        j = Q.top().j;
        l = Q.top().l;
        r = Q.top().r;
        Q.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))
                Q.push({ 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 (isdigit(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);

    if (nr > 4 * n * m)
        while (true);

    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);
                Q.push({ 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);

                    Q.push({ 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 1 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
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 1 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 976 ms 36552 KB Output is correct
12 Correct 26 ms 34260 KB Output is correct
13 Correct 384 ms 37172 KB Output is correct
14 Execution timed out 1528 ms 36472 KB Time limit exceeded
15 Halted 0 ms 0 KB -

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 1 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 976 ms 36552 KB Output is correct
12 Correct 26 ms 34260 KB Output is correct
13 Correct 384 ms 37172 KB Output is correct
14 Execution timed out 1528 ms 36472 KB Time limit exceeded
15 Halted 0 ms 0 KB -