제출 #956063

#제출 시각아이디문제언어결과실행 시간메모리
956063robertopinoConnect (CEOI06_connect)C++14
0 / 100
1 ms604 KiB
#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 = 2; 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); fore (i, 0, n) { getline(cin, board[i]); assert(sz(board[i]) == m); debug(board[i]); } #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; }; memset(dp, 63, sizeof(dp)); dp[0][0][0] = 0; n /= 2, m /= 2; debug(n, m); fore (r, 0, n) { fore (c, 0, m + 1) { // curr = r; fore (mask, 0, 1 << m) { // verity debug("verify"); bool canContinue = true; int updatedMask = 0; if (r > 0) { fore (ith, 0, m) { bool bit = updatedMask & (1 << ith); if (bit) { // bit is set if (isAFigure(r - 1, ith)) { // do nothing } else { updatedMask |= 1 << ith; if (blocked(r - 1, c, r, c)) { canContinue = false; break; } } } else { // bit isn't set if (isAFigure(r - 1, ith)) { if (isAFigure(r, ith)) { // two consecutive X's if (blocked(ith, r - 1, ith, r)) { canContinue = false; break; } else { // connect them updatedMask |= (1 << ith); } } updatedMask |= 1 << ith; } else { // do nothing } } } } debug(""); bitset<N_BITSET> updatedMaskBitset(updatedMask); bitset<N_BITSET> maskBitset(mask); auto& me = dp[r][c][mask]; debug(r, c, maskBitset, me); debug(updatedMaskBitset, canContinue); if (!canContinue) { continue; } if (c == m) { debug("next row", r + 1, 0, mask, me); umin(dp[r + 1][0][mask], me); debug(dp[r + 1][0][mask]); debug(""); continue; } if (~updatedMask & (1 << c)) { // do nothing debug("// do nothing"); umin(dp[r][c + 1][updatedMask], me); } debug(""); debug("start"); debug("create a new pair (a, b)"); if (~updatedMask & (1 << c)) { // create a new pair (a, b) // place a in c // try to place b after c int a = c; for (int b = c + 1; b < m; b++) { if (updatedMask & (1 << b) || blocked(r, b - 1, r, b)) { // there is an end here or is blocked break; } int newMask = updatedMask | (1 << a) | (1 << b); int newC = b + 1; int len = abs(a - b) + 1; // +1 ?? umin(dp[r][newC][newMask], me + len); if (isAFigure(r, b)) { break; } } } debug(""); { // continue an end debug("continue an end"); int indexNextEnd = -1; fore (ith, c, m) { if (updatedMask & (1 << ith)) { indexNextEnd = ith; break; } } debug(indexNextEnd); if (indexNextEnd != -1) { // left debug("left"); for (int ith = indexNextEnd; ith >= c; ith--) { if (ith != indexNextEnd && blocked(r, ith, r, ith + 1)) { break; } // move end from indexNextEnd to ith if possible int newMask = updatedMask; assert(updatedMask & (1 << indexNextEnd)); newMask ^= 1 << indexNextEnd; // off newMask |= 1 << ith; // on int newC = max(ith, indexNextEnd) + 1; int len = abs(indexNextEnd - ith) + 1; umin(dp[r][newC][newMask], me + len); if (isAFigure(r, ith)) { break; } } // right debug("right"); for (int ith = indexNextEnd + 1; ith < m; ith++) { if (blocked(r, ith - 1, r, ith)) { // is blocked break; } if (updatedMask & (1 << ith)) { break; } // move end from indexNextEnd to ith if possible int newMask = updatedMask; assert(updatedMask & (1 << indexNextEnd)); newMask ^= 1 << indexNextEnd; // off newMask |= 1 << ith; // on int newC = max(ith, indexNextEnd) + 1; int len = abs(indexNextEnd - ith) + 1; umin(dp[r][newC][newMask], me + len); if (isAFigure(r, ith)) { break; } } } } debug(""); { // connect two next ends if possible debug(" connect two next ends if possible"); int a = -1, b = -1; fore (ith, c, m) { if (a != -1) { if (isAFigure(r, ith)) { break; } if (blocked(r, ith - 1, r, ith)) { break; } if (updatedMask & (1 << ith)) { // second end b = ith; int newC = ith + 1; int newUpdatedMask = updatedMask ^ (1 << a) ^ (1 << b); bitset<N_BITSET> newUpdatedMaskBitset(newUpdatedMask); int len = abs(a - b) + 1; debug(a, b, newC, newUpdatedMaskBitset, me, len); umin(dp[r][newC][newUpdatedMask], me + len); break; } } else { // looking for first if (updatedMask & (1 << ith)) { a = ith; if (isAFigure(r, ith)) { break; } } } } } // anything else? debug("---------------------------------------------"); } debug(""); } debug(""); } debug(""); cout << dp[n][0][0] << '\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 timeMemoryGrader output
Fetching results...