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