Submission #958534

#	Time	Username	Problem	Language	Result	Execution time	Memory
958534		robertopino	Connect (CEOI06_connect)	C++14	80 / 100	62 ms	18404 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 = 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 bitIsActuallySet = [&] (int r, int c, int mask) -> bool {
    if (mask & (1 << r))
      return isAFigure(r, c - 1) == false;
    return isAFigure(r, c - 1) == true;
  };


  auto createNewPair = [&] (int r, int c, int mask) {
    debug("createNewPair");
    int me = dp[c][r][mask];
    int maskTmp = 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 (!bitIsActuallySet(b, c, mask)) {
          turnOffBit(maskTmp, b);  
        }

        if (blocked(b - 1, c, b, c) || !canPlaceAConnection(b, c, mask)) {
          break;
        }

        
      

      debug("place in b", b);
        int newMask = maskTmp;
        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("");
  };


  
  // everything above looks correct


  auto continueAConnection = [&] (int r, int c, int mask) {
    int me = dp[c][r][mask];

    debug("continueAConnection");
    int maskTmp = mask;
    // move next connection to c
    int index = -1;
    fore (ith, r, n) {
      if (bitIsActuallySet(ith, c, mask)) {
        index = ith;
        break;
      }
      turnOffBit(maskTmp, ith);
    }

    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 = maskTmp;
        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;
          }
          turnOffBit(maskTmp, ith);

          // move end from index to ith if possible
          int newMask = maskTmp;
          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);
          bitset<N_BITSET> newMaskBitset(newMask);
          debug(index, " -> " , ith, newR, len, cost, me, newMaskBitset);
          umin(dp[c][newR][newMask], cost);
          if (isAFigure(ith, c)) {
            break;
          }
        }
      }
      debug("");
    }
  };

  auto meetTwoConnections = [&] (int r, int c, int mask) {
    int me = dp[c][r][mask];
    int maskTmp = 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)) {
          turnOffBit(maskTmp, ith);
          continue;
        }

        debug("wtf");

        int a = r, b = ith;
        int newR = ith + 1;
        int newMask = maskTmp;
        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(a, c, mask) + additionalCost(b, c, mask);
        int cost = me + len + additionalCost(a, c, mask) + additionalCost(b, c, mask);
        debug(a, b, newR, newMaskBitset, len, cost, me);
        // 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);
          if (mask == 43 && r == 0 && c == 3) {
            debug("right here");
            bitset<N_BITSET> newMaskBitset(newMask);
            debug(r, c, maskBitset, newMaskBitset, me);

          }
          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
 */

• Subtask 1: 80 / 100