Submission #958539

#	Time	Username	Problem	Language	Result	Execution time	Memory
958539		robertopino	Connect (CEOI06_connect)	C++14	80 / 100	60 ms	9048 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 = 12, M = 40;
int dp[M][N + 1][1 << N];
 
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]);
  int foobar = 0;
  fore (i, 0, n) {
    getline(cin, board[i]);
    assert(sz(board[i]) == m);
    fore (j, 0, m) {
      foobar += board[i][j] == 'X';
    }
  }
  
  foobar /= 2;
  n /= 2, m /= 2;
  int completeMask = (1 << n) - 1;
 
  #define coord(x) (x * 2 + 1)
  auto isAFigure = [&] (int r, int c) -> bool {
    if (r < 0 || c < 0) {
      return false;
    }
    r = coord(r), c = coord(c);
    return board[r][c] == 'X';
  };
 
  auto blocked = [&] (int r1, int c1, int r2, int c2) -> bool {
    if (r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0) {
      return false;
    }
 
    r1 = coord(r1), c1 = coord(c1);
    r2 = coord(r2), c2 = coord(c2);
    bool thereIsAWall = false;
    if (r1 == r2) { // hor
      if (c1 > c2) {
        swap(c1, c2);
      }
      assert(c1 + 2 == c2);
      thereIsAWall = board[r1][c1 + 1] == '|';
    } else { // ver
      assert(c1 == c2);
      if (r1 > r2) {
        swap(r1, r2);
      }
      assert(r1 + 2 == r2);
      thereIsAWall = board[r1 + 1][c1] == '-';
    }
 
    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) {
    int me = dp[c][r][mask];
    int maskTmp = mask;
 
    if (canPlaceAConnection(r, c, mask)) { // create a new pair (a, b)
      int a = r;
      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;
        }
 
        int newMask = maskTmp;
        turnOnBit(newMask, a);
        turnOnBit(newMask, b);
        int newR = b + 1;
        int len = abs(a - b) + 1;
        int cost = me + len;
        umin(dp[c][newR][newMask], cost);
        if (isAFigure(b, c)) {
          break;
        }
      }
    }
  };
 
  auto continueAConnection = [&] (int r, int c, int mask) {
    int me = dp[c][r][mask];
 
    int maskTmp = mask;
    int index = -1;
    fore (ith, r, n) {
      if (bitIsActuallySet(ith, c, mask)) {
        index = ith;
        break;
      }
      turnOffBit(maskTmp, ith);
    }
 
    if (index != -1) {
      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;
        turnOffBit(newMask, index);
        turnOnBit(newMask, ith);
        int newR = max(ith, index) + 1;
        int len = abs(index - ith) + 1;
        int cost = me + len + additionalCost(index, c, mask);
        umin(dp[c][newR][newMask], cost);
        if (isAFigure(ith, c)) {
          break;
        }
      }
 
      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 + 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];
    int maskTmp = mask;
    if (bitIsActuallySet(r, c, mask) && !isAFigure(r, c)) {
      fore (ith, r + 1, n) {
        if (isAFigure(ith, c) || blocked(ith - 1, c, ith, c)) {
          break;
        }
        if (!bitIsActuallySet(ith, c, mask)) {
          turnOffBit(maskTmp, ith);
          continue;
        }
 
        int a = r, b = ith;
        int newR = ith + 1;
        int newMask = maskTmp;
        turnOffBit(newMask, a);
        turnOffBit(newMask, b);
        int len = abs(a - b) + 1;
        int cost = me + len + additionalCost(a, c, mask) + additionalCost(b, c, mask);
        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];
 
        if (r == n) {
          umin(dp[c + 1][0][mask], me);
          continue;
        }
 
        bool invalid = verify(r, c, mask);
        if (invalid) {
          continue;
        }
 
        if (!bitIsActuallySet(r, c, mask)) {
          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);
      }
    }
  }
  
  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