Submission #3790760


Source Code Expand

#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 i = 0; i < H; i++)
        for (int j = 0; j < W; j++) {
            if (used[i][j]) continue;
            // pick next cell greedily
            int count = 1, i0 = i, j0 = j;
            vector<P> v(K);
            v[0] = make_pair(i, j);
            used[i][j] = true;
            while (count < K) {
                int d = -1, max = 0;
                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]
                        && max < input[i1][j1]) {
                        max = input[i1][j1]; d = k;
                    }
                }
                if (d >= 0) {
                    // found next cell
                    int i1 = i0 + diry[d], j1 = j0 + dirx[d];
                    v[count++] = make_pair(i1, j1);
                    used[i1][j1] = true;
                    i0 = i1; j0 = j1;
                } else break;
            }
            if (v.size() == count) ans.insert(ans.end(), v.begin(), v.end());
        }
    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 93642
Code Size 1692 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 10530 / 1343058 8693 / 1343058 10631 / 1343058 10018 / 1343058 10396 / 1343058 8096 / 1343058 10263 / 1343058 7909 / 1343058 8861 / 1343058 8245 / 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 4 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