Submission #3041758


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 30;
// const int SIZE = 3;

int board[SIZE][SIZE],
    longestPath[SIZE][SIZE];

int dr[4] = {1, 0, -1, 0},
    dc[4] = {0, 1, 0, -1};

int randInt(int n)
{
    static random_device rnd;
    static mt19937 mt(rnd());

    return mt() % n;
}

bool isInside(int r, int c)
{
    return 0 <= r and r < SIZE and 0 <= c and c < SIZE;
}

struct Mass
{
    int row, col;

    Mass() {}
    Mass(int row, int col) : row{row}, col{col} {}

    bool operator>(const Mass& m) const
    {
        return board[row][col] > board[m.row][m.col];
    }
};

void inputBoard()
{
    for (int r = 0; r < SIZE; r++)
    {
        for (int c = 0; c < SIZE; c++)
        {
            cin >> board[r][c];
        }
    }
}

vector<Mass> restorePath(int startR, int startC)
{
    vector<Mass> path;

    int curR = startR, curC = startC;

    while (isInside(curR, curC) and longestPath[curR][curC] > 0)
    {
        path.emplace_back(curR, curC);

        int nextR = -1, nextC = -1;

        for (int i = 0; i < 4; i++)
        {
            int nr = curR + dr[i],
                nc = curC + dc[i];
            
            if (isInside(nr, nc) and longestPath[nr][nc] + 1 == longestPath[curR][curC])
            {
                nextR = nr;
                nextC = nc;
            }
        }
        curR = nextR;
        curC = nextC;
    }

    return path;
}

vector<Mass> findLongestPath()
{
    priority_queue<Mass, vector<Mass>, greater<Mass>> Q;
    memset(longestPath, -1, sizeof(longestPath));

    for (int r = 0; r < SIZE; r++)
    {
        for (int c = 0; c < SIZE; c++)
        {
            Q.push(Mass(r, c));
        }
    }

    int startR = -1, startC = -1;
    while (!Q.empty())
    {
        auto m = Q.top(); Q.pop();

        longestPath[m.row][m.col] = board[m.row][m.col] ? 1 : 0;

        if (board[m.row][m.col] == 0) continue;

        for (int i = 0; i < 4; i++)
        {
            int nr = m.row + dr[i],
                nc = m.col + dc[i];
            
            if (isInside(nr, nc) and board[nr][nc] == board[m.row][m.col] - 1)
            {
                longestPath[m.row][m.col] = max(longestPath[m.row][m.col],
                                                longestPath[nr][nc] + 1);
            }
        }

        if ((startR < 0 and startC < 0) or longestPath[m.row][m.col] > longestPath[startR][startC])
        {
            startR = m.row;
            startC = m.col;
        }
    }

    return restorePath(startR, startC);
}

vector<Mass> findGoodPath()
{
    vector<Mass> path = findLongestPath();

    int highestR = 0, highestC = 0;
    for (int r = 0; r < SIZE; r++)
    {
        for (int c = 0; c < SIZE; c++)
        {
            if (board[r][c] > board[highestR][highestR])
            {
                highestR = r;
                highestC = c;
            }
        }
    }

    if (randInt(3) == 0) path = restorePath(highestR, highestC);

    return path;
}

int main()
{
    inputBoard();

    int turn = 1;

    vector<Mass> path;
    while ((path = findLongestPath()), !path.empty())
    {
        cerr << "[turn] " << turn++ << " [path.length] " << path.size() << endl;
        /*
        for (int r = 0; r < SIZE; r++)
        {
            for (int c = 0; c < SIZE; c++)
            {
                cerr << longestPath[r][c] << " ";
            }
            cerr << endl;
        }
        */
        // cerr << " ==== debug end ==== " << endl;

        for (auto& m : path)
        {
            cout << m.row + 1 << " " << m.col + 1 << endl;
            board[m.row][m.col]--;

            // cerr << "debug: " << board[m.row][m.col] << " => " << board[m.row][m.col] - 1 << endl;

            assert(board[m.row][m.col] >= 0);
        }
    }

    return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User myusa
Language C++14 (GCC 5.4.1)
Score 575699
Code Size 3966 Byte
Status AC
Exec Time 3268 ms
Memory 640 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 59520 / 100000 55791 / 100000 58246 / 100000 56544 / 100000 57756 / 100000 57731 / 100000 56994 / 100000 59539 / 100000 57160 / 100000 56418 / 100000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 2975 ms 512 KB
subtask_01_02.txt AC 3268 ms 512 KB
subtask_01_03.txt AC 3077 ms 640 KB
subtask_01_04.txt AC 3236 ms 512 KB
subtask_01_05.txt AC 3152 ms 512 KB
subtask_01_06.txt AC 3144 ms 512 KB
subtask_01_07.txt AC 3188 ms 640 KB
subtask_01_08.txt AC 2982 ms 512 KB
subtask_01_09.txt AC 3179 ms 512 KB
subtask_01_10.txt AC 3247 ms 640 KB