답안 #958213

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958213 2024-04-05T07:34:35 Z robertopino Connect (CEOI06_connect) C++14
8 / 100
61 ms 18516 KB
#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 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;
      debug("place in a", a);
      for (int b = a + 1; b < n; b++) {
        if (blocked(b - 1, c, b, c) || !canPlaceAConnection(b, c, mask)) {
          break;
        }
        
      debug("place in b", b);
        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);
        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("");
  };


  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;
  };

  // everything above looks correct


  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);
        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;
          }

          // 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);
          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];

    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);
        int cost = me + len + 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;
  }

  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
 */
# 결과 실행 시간 메모리 Grader output
1 Partially correct 4 ms 18268 KB Partially correct (80% score). Wrong board
2 Incorrect 4 ms 18324 KB Wrong score! (36, expected 40)
3 Incorrect 3 ms 18264 KB Wrong score! (60, expected 74)
4 Incorrect 5 ms 18264 KB Wrong score! (22, expected 28)
5 Incorrect 18 ms 18400 KB Wrong score! (54, expected 102)
6 Incorrect 5 ms 18268 KB Wrong score! (108, expected 112)
7 Partially correct 4 ms 18268 KB Partially correct (80% score). Wrong board
8 Incorrect 4 ms 18268 KB Wrong score! (90, expected 94)
9 Incorrect 5 ms 18264 KB Wrong score! (2122219104, expected 132)
10 Incorrect 7 ms 18316 KB Wrong score! (146, expected 208)
11 Incorrect 5 ms 18268 KB Wrong score! (104, expected 106)
12 Incorrect 7 ms 18264 KB Wrong score! (122, expected 268)
13 Incorrect 9 ms 18268 KB Wrong score! (88, expected 208)
14 Incorrect 11 ms 18416 KB Wrong score! (2122219054, expected 462)
15 Incorrect 16 ms 18264 KB Wrong score! (2122219080, expected 422)
16 Incorrect 16 ms 18268 KB Wrong score! (468, expected 664)
17 Incorrect 25 ms 18264 KB Wrong score! (2122219092, expected 288)
18 Incorrect 48 ms 18516 KB Wrong score! (2122219064, expected 296)
19 Incorrect 61 ms 18392 KB Wrong score! (196, expected 212)
20 Incorrect 49 ms 18268 KB Wrong score! (152, expected 374)