Submission #957195

#	Time	Username	Problem	Language	Result	Execution time	Memory
957195		robertopino	Connect (CEOI06_connect)	C++14	4 / 100	1062 ms	37976 KiB

connect

#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 = 44;
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';
  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
 */

• Subtask 1: 4 / 100