Submission #4924951
Source Code Expand
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#ifdef DEBUG
#define line() cout << "[" << __LINE__ << "] ";
#define dump(i) cout << #i ": " << i << " ";
#define dumpl(i) cout << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;
int h, w, k;
bool makeUnit(vector<vector<int>> &g, vector<vector<bool>> &used, vector<pair<int, int>> &ret, int y, int x, int now)
{
ret[now] = {y, x};
used[y][x] = true;
now++;
if (now == k)
return true;
int r = min(w - 1, x + 1);
int l = max(0, x - 1);
int u = min(h - 1, y + 1);
int d = max(0, y - 1);
// cerr << u << "," << d << "," << r << "," << l << "," << y << "," << x << endl;
// cerr << "checkstart" << endl;
if (used[u][x] && used[d][x] && used[y][r] && used[y][l])
{
rep(i, now + 1)
{
// cerr << ret[i].first << "," << ret[i].second << endl;
//used[ret[i].first][ret[i].second] = false;
}
return false;
}
// cerr << "checkend" << endl;
// cerr << "pstart" << endl;
pair<int, pair<int, int>> p[4];
p[0] = {g[u][x], {u, x}};
p[1] = {g[d][x], {d, x}};
p[2] = {g[y][r], {y, r}};
p[3] = {g[y][l], {y, l}};
// cerr << "pend" << endl;
sort(p, p + 4);
int cy, cx;
for (int i = 3; i >= 0; i--)
{
cy = p[i].second.first;
cx = p[i].second.second;
if (used[cy][cx] == false)
break;
}
return makeUnit(g, used, ret, cy, cx, now);
}
int main()
{
cin >> h >> w >> k;
vector<vector<int>> g(h, vector<int>(w, 0));
vector<vector<bool>> used(h, vector<bool>(w, false));
rep(i, h)
{
string s;
cin >> s;
rep(j, w)
{
g[i][j] = s[j] - '0';
}
}
vector<vector<pair<int, int>>> ans;
int miss = 0;
//cerr << "search" << endl;
while (true)
{
int sy = rand() % h, sx = rand() % w;
vector<pair<int, int>> ret(k, {-1, -1});
// cerr << "makestart" << endl;
if (used[sy][sx] == true)
{
continue;
}
if (makeUnit(g, used, ret, sy, sx, 0))
{
ans.push_back(ret);
miss = 0;
}
else
{
miss++;
}
// cerr << "makeend" << endl;
if (miss == 100)
break;
}
cout << ans.size() << endl;
rep(i, ans.size())
{
rep(j, k)
{
cout << ans[i][j].first + 1 << " " << ans[i][j].second + 1 << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
sbite |
Language |
C++14 (GCC 5.4.1) |
Score |
270895 |
Code Size |
2957 Byte |
Status |
AC |
Exec Time |
4 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 |
25647 / 1343058 |
22696 / 1343058 |
28988 / 1343058 |
25115 / 1343058 |
27526 / 1343058 |
28673 / 1343058 |
26962 / 1343058 |
26936 / 1343058 |
27040 / 1343058 |
31312 / 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 |
4 ms |
256 KB |
subtask_01_02.txt |
AC |
4 ms |
256 KB |
subtask_01_03.txt |
AC |
4 ms |
256 KB |
subtask_01_04.txt |
AC |
4 ms |
256 KB |
subtask_01_05.txt |
AC |
4 ms |
256 KB |
subtask_01_06.txt |
AC |
4 ms |
256 KB |
subtask_01_07.txt |
AC |
4 ms |
256 KB |
subtask_01_08.txt |
AC |
4 ms |
256 KB |
subtask_01_09.txt |
AC |
4 ms |
256 KB |
subtask_01_10.txt |
AC |
4 ms |
256 KB |