Submission #3790928


Source Code Expand

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int H, W, K;
int input[50][50];

typedef pair<int, int> P;

int dirx[] = {1, -1, 0, 0}, diry[] = {0, 0, 1, -1};

vector<P> solve() {
    bool used[H][W] = {};
    vector<P> ans;
    for (int start_min = 9; start_min > 0; start_min--)
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++) {
                if (used[i][j] || input[i][j] < start_min) continue;
                // greedy search
                vector<P> v(K);
                priority_queue<pair<int, P> > pq;
                pq.push(make_pair(input[i][j], make_pair(i, j)));
                int count = 0;
                while (!pq.empty()) {
                    int i0 = pq.top().second.first, j0 = pq.top().second.second;
                    pq.pop();
                    if (used[i0][j0]) continue;
                    v[count++] = make_pair(i0, j0);
                    used[i0][j0] = true;
                    if (count == K) break;

                    for (int k = 0; k < 4; k++) {
                        int i1 = i0 + diry[k], j1 = j0 + dirx[k];
                        if (0 <= i1 && i1 < H && 0 <= j1 && j1 < W && !used[i1][j1]
                            && input[i1][j1] > start_min/4) {
                            pq.push(make_pair(input[i1][j1], make_pair(i1, j1)));
                        }
                    }
                }
                if (v.size() == count) ans.insert(ans.end(), v.begin(), v.end());
                else for (auto p : v) used[p.first][p.second] = false;
            }
    return ans;
}

int main() {
    cin >> H >> W >> K;
    for (int i = 0; i < H; i++) {
        string s; cin >> s;
        for (int j = 0; j < W; j++) input[i][j] = s[j]-'0';
    }
    vector<P> v = solve();
    cout << v.size() / K << endl;
    for (auto x : v) cout << x.first + 1 << ' ' << x.second + 1 << endl;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User kozima
Language C++14 (GCC 5.4.1)
Score 801664
Code Size 1959 Byte
Status AC
Exec Time 5 ms
Memory 256 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 82404 / 1343058 76463 / 1343058 79564 / 1343058 77239 / 1343058 88599 / 1343058 76910 / 1343058 84636 / 1343058 73094 / 1343058 82258 / 1343058 80497 / 1343058
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 5 ms 256 KB
subtask_01_02.txt AC 5 ms 256 KB
subtask_01_03.txt AC 5 ms 256 KB
subtask_01_04.txt AC 5 ms 256 KB
subtask_01_05.txt AC 5 ms 256 KB
subtask_01_06.txt AC 5 ms 256 KB
subtask_01_07.txt AC 5 ms 256 KB
subtask_01_08.txt AC 5 ms 256 KB
subtask_01_09.txt AC 5 ms 256 KB
subtask_01_10.txt AC 5 ms 256 KB