Submission #956063

#	Time	Username	Problem	Language	Result	Execution time	Memory
956063		robertopino	Connect (CEOI06_connect)	C++14	0 / 100	1 ms	604 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 << 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
 */

• Subtask 1: 0 / 100