제출 #957232

#제출 시각아이디문제언어결과실행 시간메모리
957232robertopinoConnect (CEOI06_connect)C++14
8 / 100
57 ms8796 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][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; 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 ith, int c, int mask) -> bool { if ((~mask & (1 << ith)) && isAFigure(ith, 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 ith, int c, int mask) -> bool { if (mask & (1 << ith)) { return isAFigure(ith, c - 1) ? true : false; } else { return isAFigure(ith, 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; for (int b = r + 1; b < n; b++) { if (blocked(b - 1, c, b, c) || !canPlaceAConnection(b, c, mask)) { break; } 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); // 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 ith, int c, int mask) -> bool { if (mask & (1 << ith)) return isAFigure(ith, c - 1) == false; return isAFigure(ith, c - 1) == true; }; 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); 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); 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); // 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; } cout << dp[m][0][mask] - foobar << '\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...