답안 #958211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958211 2024-04-05T07:26:55 Z robertopino Connect (CEOI06_connect) C++14
4 / 100
500 ms 36956 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 = 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;
  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 << 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 c, int mask) -> bool {
    if ((~mask & (1 << c)) && isAFigure(r - 1, c)) {
      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 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 << c)) {
      return isAFigure(r - 1, c) ? true : false;
    } else {
      return isAFigure(r - 1, c) ? 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;
      debug("place in a", a);
      for (int b = c + 1; b < m; b++) {
        if (blocked(r, b - 1, r, b) || !canPlaceAConnection(r, b, mask)) {
          break;
        }
      debug("place in b", b);
        
        // int newMask = mask | (1 << a) | (1 << b);
        int newMask = mask;
        turnOnBit(newMask, a);
        turnOnBit(newMask, b);
        int newC = 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, 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 c, int mask) -> bool {
    if (mask & (1 << c))
      return isAFigure(r - 1, c) == false;
    return isAFigure(r - 1, c) == true;
  };
 
  
  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);
        int cost = me + len + 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);
          int cost = me + len + 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);
        int cost = me + len + 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;
  }
  
  // int sol = dp[n][0][mask] - foobar;
  int sol = (dp[n][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 3 ms 18300 KB Wrong score! (36, expected 40)
3 Incorrect 4 ms 18268 KB Wrong score! (2122219110, expected 74)
4 Incorrect 3 ms 18320 KB Wrong score! (26, expected 28)
5 Incorrect 17 ms 18268 KB Wrong score! (64, expected 102)
6 Runtime error 18 ms 36952 KB Execution killed with signal 11
7 Incorrect 177 ms 18524 KB Wrong score! (0, expected 72)
8 Runtime error 130 ms 36824 KB Execution killed with signal 11
9 Runtime error 44 ms 36944 KB Execution killed with signal 11
10 Runtime error 18 ms 36956 KB Execution killed with signal 11
11 Execution timed out 1035 ms 18268 KB Time limit exceeded
12 Runtime error 19 ms 36912 KB Execution killed with signal 11
13 Runtime error 80 ms 36944 KB Execution killed with signal 11
14 Runtime error 20 ms 36956 KB Execution killed with signal 11
15 Runtime error 101 ms 36832 KB Execution killed with signal 11
16 Runtime error 18 ms 36956 KB Execution killed with signal 11
17 Execution timed out 1055 ms 18264 KB Time limit exceeded
18 Runtime error 19 ms 36900 KB Execution killed with signal 11
19 Runtime error 21 ms 36952 KB Execution killed with signal 11
20 Runtime error 19 ms 36956 KB Execution killed with signal 11