| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 957189 | robertopino | Connect (CEOI06_connect) | C++14 | 1 ms | 608 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 12, M = 40;
int dp[M][N][1 << N];
const int N_BITSET = 7;
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;
cin.ignore();
cin.ignore();
vector<string> board(n);
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 << m) - 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, 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 ith, int mask) -> bool {
// if (~mask & (1 << ith) && isAFigure(r - 1, ith)) {
// return true;
// }
// return false;
// };
// auto verify = [&] (int r, int c, int mask) -> bool {
// bool invalid = false;
// if (r > 0) {
// fore (ith, c, m) {
// bool bit = mask & (1 << ith);
// invalid |= bit & !isAFigure(r - 1, ith) & blocked(r - 1, ith, r, ith);
// invalid |= !bit & isAFigure(r - 1, ith) & blocked(r - 1, ith, r, ith);
// }
// }
// return invalid;
// };
// auto canPlaceAConnection = [&] (int r, int ith, int mask) -> bool {
// if (mask & (1 << ith)) {
// return isAFigure(r - 1, ith) ? true : false;
// } else {
// return isAFigure(r - 1, ith) ? false : true;
// }
// };
// auto createNewPair = [&] (int r, int c, int mask) {
// debug("createNewPair");
// int me = dp[r][c][mask];
// if (canPlaceAConnection(r, c, mask)) { // create a new pair (a, b)
// int a = c;
// for (int b = c + 1; b < m; b++) {
// if (blocked(r, b - 1, r, b) || !canPlaceAConnection(r, b, mask)) {
// break;
// }
// int newMask = mask | (1 << a) | (1 << b);
// int newC = b + 1;
// int len = abs(a - b) + 1;
// int cost = me + (len * 2 - 1);
// bitset<N_BITSET> newMaskBitset(newMask);
// debug(a, b, newMaskBitset, newC, len, cost);
// umin(dp[r][newC][newMask], cost);
// if (isAFigure(r, b)) {
// break;
// }
// }
// }
// debug("");
// debug("");
// };
// // auto bitIsActuallySet = [&] (int r, int ith, int mask) -> bool {
// // if (mask & (1 << ith))
// // return true;
// // return isAFigure(r - 1, ith);
// // };
// auto bitIsActuallySet = [&] (int r, int ith, int mask) -> bool {
// if (mask & (1 << ith))
// return isAFigure(r - 1, ith) == false;
// return isAFigure(r - 1, ith) == true;
// };
// auto turnOffBit = [&] (int& mask, int ith) {
// mask &= completeMask ^ (1 << ith);
// };
// auto turnOnBit = [&] (int& mask, int ith) {
// mask |= (1 << ith);
// };
// auto continueAConnection = [&] (int r, int c, int mask) {
// int me = dp[r][c][mask];
// debug("continueAConnection");
// // move next connection to c
// int index = -1;
// fore (ith, c, m) {
// if (bitIsActuallySet(r, ith, mask)) {
// index = ith;
// break;
// }
// }
// debug(index);
// if (index != -1) {
// debug("left");
// for (int ith = index; ith >= c; ith--) {
// if (ith != index && (blocked(r, ith, r, ith + 1) || bitIsActuallySet(r, ith, 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 newC = max(ith, index) + 1;
// int len = abs(index - ith) + 1;
// int cost = me + (len * 2 - 1) + 1 + additionalCost(r, index, mask);
// debug(ith, newC, len, cost, newMaskBitset);
// umin(dp[r][newC][newMask], cost);
// if (isAFigure(r, ith)) {
// break;
// }
// }
// // right
// debug("right");
// if (!isAFigure(r, c)) {
// for (int ith = index + 1; ith < m; ith++) {
// if (bitIsActuallySet(r, ith, mask) || blocked(r, ith - 1, r, ith)) { // is blocked
// break;
// }
// // move end from index to ith if possible
// int newMask = mask;
// turnOffBit(newMask, index);
// turnOnBit(newMask, ith);
// int newC = max(ith, index) + 1;
// int len = abs(index - ith) + 1;
// int cost = me + (len * 2 - 1) + 1 + additionalCost(r, index, mask);
// umin(dp[r][newC][newMask], cost);
// if (isAFigure(r, ith)) {
// break;
// }
// }
// }
// }
// };
// auto meetTwoConnections = [&] (int r, int c, int mask) {
// int me = dp[r][c][mask];
// debug("meetTwoConnections");
// if (bitIsActuallySet(r, c, mask) && !isAFigure(r, c)) {
// fore (ith, c + 1, m) {
// if (isAFigure(r, ith) || blocked(r, ith - 1, r, ith)) {
// break;
// }
// if (!bitIsActuallySet(r, ith, mask)) {
// continue;
// }
// int a = c, b = ith;
// int newC = ith + 1;
// int newMask = mask;
// turnOffBit(newMask, a);
// turnOffBit(newMask, b);
// bitset<N_BITSET> newMaskBitset(newMask);
// int len = abs(a - b) + 1;
// int cost = me + (len * 2 - 1) + 2 + additionalCost(r, a, mask) + additionalCost(r, b, mask);
// debug(a, b, newC, newMaskBitset, me, len);
// umin(dp[r][newC][newMask], cost);
// break;
// }
// }
// };
// memset(dp, 63, sizeof(dp));
// dp[0][0][0] = 0;
// fore (r, 0, n) {
// fore (c, 0, m + 1) {
// fore (mask, 0, 1 << m) {
// auto me = dp[r][c][mask];
// bitset<N_BITSET> maskBitset(mask);
// debug(r, c, mask, me);
// if (c == m) {
// debug("next row");
// umin(dp[r + 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, c);
// umin(dp[r][c + 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, m) {
// if (isAFigure(n - 1, i))
// mask |= 1 << i;
// }
// debug(*min_element(all(dp[n][0])));
// cout << dp[n][0][mask] - foobar << '\n';
cout << 10 << endl;
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
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||