#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for (auto i = (l) - ((l) > (r)); i != (r) - ((l) > (r)); i += 1 - 2 * ((l) > (r)))
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define pb push_back
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ld = long double;
using lli = long long;
using ii = pair<int, int>;
const int N = 13, M = 40;
int dp[M][N + 1][1 << N];
const int N_BITSET = 9;
template <class T>
bool umin(T& a, T b) {
return (a = min(a, b)) == b;
}
int main() {
cin.tie(0)->sync_with_stdio(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> board(n);
getline(cin, board[0]);
debug(n, m);
int foobar = 0;
fore (i, 0, n) {
getline(cin, board[i]);
assert(sz(board[i]) == m);
debug(board[i]);
fore (j, 0, m) {
foobar += board[i][j] == 'X';
}
}
foobar /= 2;
n /= 2, m /= 2;
debug(n, m);
int completeMask = (1 << n) - 1;
#define coord(x) (x * 2 + 1)
auto isAFigure = [&] (int r, int c) -> bool {
if (r < 0 || c < 0) {
debug("isAFigure: Coordinates out of range");
return false;
}
debug(r, c);
r = coord(r), c = coord(c);
debug(r, c);
debug(r, c, board[r][c]);
return board[r][c] == 'X';
};
auto blocked = [&] (int r1, int c1, int r2, int c2) -> bool {
debug(r1, c1, r2, c2);
if (r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0) {
debug("blocked: Coordinates out of range");
return false;
}
r1 = coord(r1), c1 = coord(c1);
r2 = coord(r2), c2 = coord(c2);
bool thereIsAWall = false;
if (r1 == r2) { // hor
debug("horizontal");
if (c1 > c2) {
swap(c1, c2);
}
assert(c1 + 2 == c2);
thereIsAWall = board[r1][c1 + 1] == '|';
} else { // ver
debug("vertical");
assert(c1 == c2);
if (r1 > r2) {
swap(r1, r2);
}
assert(r1 + 2 == r2);
thereIsAWall = board[r1 + 1][c1] == '-';
}
debug(r1, c1, r2, c2, thereIsAWall);
return thereIsAWall;
};
auto additionalCost = [&] (int r, int c, int mask) -> bool {
if ((~mask & (1 << r)) && isAFigure(r, c - 1)) {
return true;
}
return false;
};
// ?
auto verify = [&] (int r, int c, int mask) -> bool {
bool invalid = false;
if (c > 0) {
fore (ith, r, n) {
bool bit = mask & (1 << ith);
invalid |= bit & !isAFigure(ith, c - 1) & blocked(ith, c - 1, ith, c);
invalid |= !bit & isAFigure(ith, c - 1) & blocked(ith, c - 1, ith, c);
}
}
return invalid;
};
auto turnOffBit = [&] (int& mask, int ith) {
mask &= completeMask ^ (1 << ith);
};
auto turnOnBit = [&] (int& mask, int ith) {
mask |= (1 << ith);
};
auto canPlaceAConnection = [&] (int r, int c, int mask) -> bool {
if (mask & (1 << r)) {
return isAFigure(r, c - 1) ? true : false;
} else {
return isAFigure(r, c - 1) ? false : true;
}
};
auto createNewPair = [&] (int r, int c, int mask) {
debug("createNewPair");
int me = dp[c][r][mask];
if (canPlaceAConnection(r, c, mask)) { // create a new pair (a, b)
int a = r;
debug("place in a", a);
for (int b = a + 1; b < n; b++) {
if (blocked(b - 1, c, b, c) || !canPlaceAConnection(b, c, mask)) {
break;
}
debug("place in b", b);
int newMask = mask;
turnOnBit(newMask, a);
turnOnBit(newMask, b);
int newR = b + 1;
int len = abs(a - b) + 1;
// int cost = me + (len * 2 - 1);
int cost = me + len;
// bitset<N_BITSET> newMaskBitset(newMask);
// debug(a, b, newMaskBitset, newR, len, cost);
umin(dp[c][newR][newMask], cost);
if (isAFigure(b, c)) {
break;
}
}
}
debug("");
debug("");
};
auto bitIsActuallySet = [&] (int r, int c, int mask) -> bool {
if (mask & (1 << r))
return isAFigure(r, c - 1) == false;
return isAFigure(r, c - 1) == true;
};
// everything above looks correct
auto continueAConnection = [&] (int r, int c, int mask) {
int me = dp[c][r][mask];
debug("continueAConnection");
// move next connection to c
int index = -1;
fore (ith, r, n) {
if (bitIsActuallySet(ith, c, mask)) {
index = ith;
break;
}
}
debug(index);
if (index != -1) {
debug("up");
for (int ith = index; ith >= r; ith--) {
if (ith != index && (blocked(ith, c, ith + 1, c) || bitIsActuallySet(ith, c, mask))) {
break;
}
// move connection from index to ith if possible
int newMask = mask;
debug(index, ith);
debug(newMask);
turnOffBit(newMask, index);
turnOnBit(newMask, ith);
debug(newMask);
bitset<N_BITSET> newMaskBitset(newMask);
int newR = max(ith, index) + 1;
int len = abs(index - ith) + 1;
// int cost = me + (len * 2 - 1) + 1 + additionalCost(index, c, mask);
int cost = me + len + additionalCost(index, c, mask);
debug(ith, newR, len, cost, newMaskBitset);
umin(dp[c][newR][newMask], cost);
if (isAFigure(ith, c)) {
break;
}
}
debug("down");
if (!isAFigure(r, c)) {
for (int ith = index + 1; ith < n; ith++) {
if (bitIsActuallySet(ith, c, mask) || blocked(ith - 1, c, ith, c)) { // is blocked
break;
}
// move end from index to ith if possible
int newMask = mask;
turnOffBit(newMask, index);
turnOnBit(newMask, ith);
int newR = max(ith, index) + 1;
int len = abs(index - ith) + 1;
// int cost = me + (len * 2 - 1) + 1 + additionalCost(index, c, mask);
int cost = me + len + additionalCost(index, c, mask);
umin(dp[c][newR][newMask], cost);
if (isAFigure(ith, c)) {
break;
}
}
}
}
};
auto meetTwoConnections = [&] (int r, int c, int mask) {
int me = dp[c][r][mask];
debug("meetTwoConnections");
if (bitIsActuallySet(r, c, mask) && !isAFigure(r, c)) {
fore (ith, r + 1, n) {
debug(ith);
if (isAFigure(ith, c) || blocked(ith - 1, c, ith, c)) {
break;
}
debug("here");
if (!bitIsActuallySet(ith, c, mask)) {
continue;
}
debug("wtf");
int a = r, b = ith;
int newR = ith + 1;
int newMask = mask;
turnOffBit(newMask, a);
turnOffBit(newMask, b);
bitset<N_BITSET> newMaskBitset(newMask);
int len = abs(a - b) + 1;
debug(a, b);
// int cost = me + (len * 2 - 1) + 2 + additionalCost(a, c, mask) + additionalCost(b, c, mask);
int cost = me + len + additionalCost(a, c, mask) + additionalCost(b, c, mask);
// debug(a, b, newR, newMaskBitset, me, len);
umin(dp[c][newR][newMask], cost);
break;
}
}
};
memset(dp, 63, sizeof(dp));
dp[0][0][0] = 0;
fore (c, 0, m) {
fore (r, 0, n + 1) {
fore (mask, 0, 1 << n) {
auto me = dp[c][r][mask];
bitset<N_BITSET> maskBitset(mask);
debug(c, r, mask, me);
if (r == n) {
debug("next row");
umin(dp[c + 1][0][mask], me);
continue;
}
bool invalid = verify(r, c, mask);
if (invalid) {
debug("invalid, cannot continue");
continue;
}
if (!bitIsActuallySet(r, c, mask)) {
debug("do nothing");
int newMask = mask;
turnOffBit(newMask, r);
umin(dp[c][r + 1][newMask], me);
}
createNewPair(r, c, mask);
continueAConnection(r, c, mask);
meetTwoConnections(r, c, mask);
debug("---------------------------------------------");
}
debug("");
}
debug("");
}
debug("");
int mask = 0;
fore (i, 0, n) {
if (isAFigure(i, m - 1))
mask |= 1 << i;
}
int sol = (dp[m][0][mask] - foobar) * 2;
cout << sol << '\n';
return 0;
}
/* Please, check the following:
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* write down your ideas
* DON'T get stuck on ONE APPROACH!
* ASK for HELP from your TEAMMATES
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
4 ms |
18268 KB |
Partially correct (80% score). Wrong board |
| 2 |
Incorrect |
4 ms |
18324 KB |
Wrong score! (36, expected 40) |
| 3 |
Incorrect |
3 ms |
18264 KB |
Wrong score! (60, expected 74) |
| 4 |
Incorrect |
5 ms |
18264 KB |
Wrong score! (22, expected 28) |
| 5 |
Incorrect |
18 ms |
18400 KB |
Wrong score! (54, expected 102) |
| 6 |
Incorrect |
5 ms |
18268 KB |
Wrong score! (108, expected 112) |
| 7 |
Partially correct |
4 ms |
18268 KB |
Partially correct (80% score). Wrong board |
| 8 |
Incorrect |
4 ms |
18268 KB |
Wrong score! (90, expected 94) |
| 9 |
Incorrect |
5 ms |
18264 KB |
Wrong score! (2122219104, expected 132) |
| 10 |
Incorrect |
7 ms |
18316 KB |
Wrong score! (146, expected 208) |
| 11 |
Incorrect |
5 ms |
18268 KB |
Wrong score! (104, expected 106) |
| 12 |
Incorrect |
7 ms |
18264 KB |
Wrong score! (122, expected 268) |
| 13 |
Incorrect |
9 ms |
18268 KB |
Wrong score! (88, expected 208) |
| 14 |
Incorrect |
11 ms |
18416 KB |
Wrong score! (2122219054, expected 462) |
| 15 |
Incorrect |
16 ms |
18264 KB |
Wrong score! (2122219080, expected 422) |
| 16 |
Incorrect |
16 ms |
18268 KB |
Wrong score! (468, expected 664) |
| 17 |
Incorrect |
25 ms |
18264 KB |
Wrong score! (2122219092, expected 288) |
| 18 |
Incorrect |
48 ms |
18516 KB |
Wrong score! (2122219064, expected 296) |
| 19 |
Incorrect |
61 ms |
18392 KB |
Wrong score! (196, expected 212) |
| 20 |
Incorrect |
49 ms |
18268 KB |
Wrong score! (152, expected 374) |
