제출 #572647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572647		Plurm	Mars (APIO22_mars)	C++17	36 / 100	2486 ms	3528 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;

void dfs(int N, map<pair<int, int>, vector<pair<int, int>>> &g,
         vector<string> &table, int i, int j, int &idx, const string &code) {
  if (i >= 2 * N + 1 || j >= 2 * N + 1)
    return;
  table[i][j] = code[idx];
  idx++;
  for (auto nxt : g[{i, j}]) {
    dfs(N, g, table, nxt.first, nxt.second, idx, code);
  }
}

bool dfsw(int N, map<pair<int, int>, vector<pair<int, int>>> &g,
          map<pair<int, int>, int> &w, int i, int j) {
  if (i >= 2 * N + 1 || j >= 2 * N + 1)
    return false;
  for (auto nxt : g[{i, j}]) {
    if (dfsw(N, g, w, nxt.first, nxt.second))
      w[{i, j}]++;
    w[{i, j}] += w[nxt];
  }
  return true;
}

void dfscc(int N, vector<vector<bool>> &found, vector<string> &table, int i,
           int j) {
  if (found[i][j])
    return;
  if (table[i][j] != '1')
    return;
  found[i][j] = true;
  for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
      if (abs(dx + dy) == 1 && 0 <= i + dx && i + dx < 2 * N + 1 && 0 <= j + dy &&
          j + dy < 2 * N + 1) {
        dfscc(N, found, table, i + dx, j + dy);
      }
    }
  }
}

std::string process(std::vector<std::vector<std::string>> a, int i, int j,
                    int k, int n) {
  map<pair<int, int>, vector<pair<int, int>>> g;
  map<pair<int, int>, int> w;
  g[{0, 2}] = {{1, 3}, {2, 3}, {0, 4}, {0, 3}};
  g[{0, 4}] = {{2, 6}, {1, 5}, {0, 6}, {0, 5}};
  g[{0, 6}] = {{0, 7}, {2, 8}, {1, 7}, {0, 8}};
  g[{0, 8}] = {{2, 10}, {0, 9}, {0, 10}};
  g[{0, 10}] = {{1, 12}, {0, 12}, {0, 11}};
  g[{0, 12}] = {{2, 14}, {0, 13}, {0, 14}};
  g[{0, 14}] = {{0, 15}, {0, 16}, {1, 15}};
  g[{0, 16}] = {{1, 17}, {1, 18}, {0, 17}, {0, 18}};
  g[{0, 18}] = {{1, 19}, {0, 20}, {1, 20}, {0, 19}};
  g[{1, 2}] = {{3, 4}, {2, 4}, {1, 4}};
  g[{1, 4}] = {{1, 6}};
  g[{1, 6}] = {{3, 8}, {1, 8}};
  g[{1, 8}] = {{3, 9}, {1, 10}, {3, 10}, {1, 9}};
  g[{1, 10}] = {{2, 12}, {1, 11}};
  g[{1, 12}] = {{3, 13}, {1, 13}, {2, 13}, {1, 14}};
  g[{1, 14}] = {{3, 16}, {1, 16}};
  g[{1, 16}] = {{2, 17}, {3, 18}, {2, 18}};
  g[{1, 18}] = {{3, 20}, {2, 19}, {2, 20}};
  g[{2, 0}] = {{3, 2}, {4, 0}, {3, 0}};
  g[{2, 1}] = {{3, 1}, {4, 1}, {3, 3}, {4, 3}};
  g[{2, 2}] = {{4, 2}, {4, 4}};
  g[{2, 4}] = {{2, 5}, {3, 6}};
  g[{2, 6}] = {{4, 7}, {3, 7}, {2, 7}};
  g[{2, 8}] = {{4, 9}, {4, 10}, {2, 9}};
  g[{2, 10}] = {{2, 11}, {3, 12}};
  g[{2, 12}] = {{3, 14}, {4, 13}};
  g[{2, 14}] = {{3, 15}, {2, 15}, {2, 16}};
  g[{2, 16}] = {{4, 17}, {4, 18}};
  g[{2, 18}] = {{4, 19}, {4, 20}};
  g[{3, 4}] = {{5, 6}, {3, 5}};
  g[{3, 6}] = {{5, 7}, {5, 8}};
  g[{3, 8}] = {{5, 10}};
  g[{3, 10}] = {{4, 11}, {3, 11}, {4, 12}, {5, 12}};
  g[{3, 12}] = {{5, 14}};
  g[{3, 14}] = {{4, 16}, {4, 15}};
  g[{3, 16}] = {{5, 17}, {3, 17}, {5, 18}};
  g[{3, 18}] = {{5, 19}, {3, 19}};
  g[{4, 0}] = {{6, 2}, {5, 0}, {6, 0}};
  g[{4, 1}] = {{6, 3}, {5, 1}, {6, 1}};
  g[{4, 2}] = {{5, 3}, {6, 4}, {5, 2}};
  g[{4, 3}] = {{4, 5}, {6, 5}};
  g[{4, 4}] = {{5, 4}, {5, 5}, {4, 6}, {6, 6}};
  g[{4, 6}] = {{6, 7}, {4, 8}};
  g[{4, 8}] = {{6, 9}, {5, 9}};
  g[{4, 10}] = {{5, 11}, {6, 12}};
  g[{4, 12}] = {{4, 14}, {6, 13}};
  g[{4, 14}] = {{6, 15}, {5, 15}, {5, 16}};
  g[{4, 16}] = {{6, 18}};
  g[{4, 18}] = {{5, 20}, {6, 20}};
  g[{5, 6}] = {{6, 8}, {7, 7}};
  g[{5, 8}] = {{6, 10}};
  g[{5, 10}] = {{7, 12}};
  g[{5, 12}] = {{7, 13}, {5, 13}, {6, 14}};
  g[{5, 14}] = {{7, 16}};
  g[{5, 16}] = {{7, 17}, {6, 17}};
  g[{5, 18}] = {{7, 20}, {6, 19}, {7, 19}};
  g[{6, 0}] = {{8, 0}, {7, 0}};
  g[{6, 1}] = {{7, 1}, {7, 3}, {8, 2}, {8, 1}};
  g[{6, 2}] = {{7, 2}, {7, 4}, {8, 4}, {8, 3}};
  g[{6, 3}] = {{8, 5}, {7, 5}};
  g[{6, 4}] = {{8, 6}};
  g[{6, 5}] = {{7, 6}, {8, 7}};
  g[{6, 6}] = {{7, 8}, {8, 8}};
  g[{6, 8}] = {{8, 9}, {7, 9}};
  g[{6, 10}] = {{7, 11}, {6, 11}, {8, 12}};
  g[{6, 12}] = {{7, 14}, {8, 13}};
  g[{6, 14}] = {{6, 16}};
  g[{6, 16}] = {{8, 18}};
  g[{6, 18}] = {{8, 19}, {8, 20}};
  g[{7, 8}] = {{9, 9}, {7, 10}, {9, 10}};
  g[{7, 10}] = {{9, 12}};
  g[{7, 12}] = {{9, 14}};
  g[{7, 14}] = {{7, 15}, {8, 15}, {9, 15}, {8, 16}};
  g[{7, 16}] = {{8, 17}, {7, 18}, {9, 17}};
  g[{7, 18}] = {{9, 20}, {9, 19}};
  g[{8, 0}] = {{9, 2}, {10, 2}, {9, 1}, {10, 0}, {9, 0}};
  g[{8, 1}] = {{10, 1}};
  g[{8, 2}] = {{10, 4}};
  g[{8, 3}] = {{9, 5}, {9, 3}, {10, 3}};
  g[{8, 4}] = {{9, 4}, {10, 5}, {9, 6}};
  g[{8, 5}] = {{10, 6}, {9, 7}};
  g[{8, 6}] = {{10, 8}, {10, 7}};
  g[{8, 7}] = {{10, 9}, {9, 8}};
  g[{8, 8}] = {{8, 10}, {10, 10}};
  g[{8, 10}] = {{8, 11}, {10, 11}, {9, 11}, {10, 12}};
  g[{8, 12}] = {{10, 14}, {9, 13}, {8, 14}};
  g[{8, 14}] = {{10, 15}, {10, 16}};
  g[{8, 16}] = {{10, 18}, {10, 17}};
  g[{8, 18}] = {{10, 20}, {10, 19}};
  g[{9, 10}] = {{11, 10}, {11, 12}};
  g[{9, 12}] = {{11, 14}};
  g[{9, 14}] = {{9, 16}, {11, 16}};
  g[{9, 16}] = {{11, 17}, {9, 18}};
  g[{9, 18}] = {{11, 20}, {11, 19}};
  g[{10, 0}] = {{11, 1}, {12, 2}, {11, 0}, {12, 0}};
  g[{10, 1}] = {{12, 1}};
  g[{10, 2}] = {{12, 3}, {11, 2}};
  g[{10, 3}] = {{11, 4}, {11, 3}, {12, 5}};
  g[{10, 4}] = {{12, 6}, {12, 4}};
  g[{10, 5}] = {{11, 7}, {11, 5}, {11, 6}};
  g[{10, 6}] = {{11, 8}, {12, 7}};
  g[{10, 7}] = {{11, 9}, {12, 8}};
  g[{10, 8}] = {{12, 9}};
  g[{10, 9}] = {{12, 11}, {12, 10}};
  g[{10, 10}] = {{11, 11}, {12, 12}};
  g[{10, 12}] = {{12, 13}, {10, 13}, {12, 14}};
  g[{10, 14}] = {{12, 16}};
  g[{10, 16}] = {{12, 17}, {12, 18}};
  g[{10, 18}] = {{12, 19}, {12, 20}};
  g[{11, 12}] = {{13, 14}, {11, 13}};
  g[{11, 14}] = {{13, 16}, {11, 15}, {13, 15}};
  g[{11, 16}] = {{13, 18}, {11, 18}};
  g[{11, 18}] = {{13, 19}, {13, 20}};
  g[{12, 0}] = {{14, 2}, {13, 0}, {14, 0}};
  g[{12, 1}] = {{13, 3}, {13, 1}, {13, 2}, {14, 1}};
  g[{12, 2}] = {{14, 3}};
  g[{12, 3}] = {{14, 5}};
  g[{12, 4}] = {{13, 6}, {13, 4}, {14, 4}, {13, 5}, {14, 6}};
  g[{12, 5}] = {{14, 7}};
  g[{12, 6}] = {{14, 8}, {13, 7}};
  g[{12, 7}] = {{14, 9}};
  g[{12, 8}] = {{13, 10}, {14, 10}, {13, 8}, {13, 9}};
  g[{12, 9}] = {{14, 11}};
  g[{12, 10}] = {{14, 12}};
  g[{12, 11}] = {{13, 13}, {13, 12}, {13, 11}};
  g[{12, 12}] = {{14, 13}, {14, 14}};
  g[{12, 14}] = {{14, 16}, {12, 15}};
  g[{12, 16}] = {{14, 17}, {13, 17}, {14, 18}};
  g[{12, 18}] = {{14, 20}, {14, 19}};
  g[{13, 14}] = {{15, 16}, {15, 15}};
  g[{13, 16}] = {{15, 17}, {15, 18}};
  g[{13, 18}] = {{15, 19}, {15, 20}};
  g[{14, 0}] = {{15, 0}, {16, 0}, {15, 1}};
  g[{14, 1}] = {{16, 2}, {16, 1}};
  g[{14, 2}] = {{15, 2}, {16, 4}, {16, 3}};
  g[{14, 3}] = {{16, 5}, {15, 3}};
  g[{14, 4}] = {{15, 5}, {15, 6}, {15, 4}};
  g[{14, 5}] = {{16, 6}};
  g[{14, 6}] = {{15, 8}, {16, 8}, {15, 7}};
  g[{14, 7}] = {{15, 9}, {16, 9}, {16, 7}};
  g[{14, 8}] = {{15, 10}, {16, 10}};
  g[{14, 9}] = {{16, 11}};
  g[{14, 10}] = {{15, 11}, {15, 12}};
  g[{14, 11}] = {{15, 13}, {16, 13}};
  g[{14, 12}] = {{16, 12}};
  g[{14, 13}] = {{16, 15}, {14, 15}, {16, 14}};
  g[{14, 14}] = {{16, 16}, {15, 14}};
  g[{14, 16}] = {{16, 18}, {16, 17}};
  g[{14, 18}] = {{16, 20}, {16, 19}};
  g[{15, 16}] = {{17, 18}, {17, 16}};
  g[{15, 18}] = {{17, 20}, {17, 19}};
  g[{16, 0}] = {{17, 0}, {18, 0}, {17, 1}};
  g[{16, 1}] = {{18, 3}, {18, 1}};
  g[{16, 2}] = {{17, 2}, {17, 4}, {18, 2}};
  g[{16, 3}] = {{17, 5}, {17, 3}, {18, 5}};
  g[{16, 4}] = {{18, 4}};
  g[{16, 5}] = {{17, 7}, {17, 6}, {18, 6}};
  g[{16, 6}] = {{17, 8}, {18, 8}, {18, 7}};
  g[{16, 7}] = {{17, 9}, {18, 9}};
  g[{16, 8}] = {{18, 10}};
  g[{16, 9}] = {{18, 11}};
  g[{16, 10}] = {{17, 12}, {17, 10}, {17, 11}};
  g[{16, 11}] = {{17, 13}, {18, 12}};
  g[{16, 12}] = {{18, 14}, {18, 13}};
  g[{16, 13}] = {{17, 14}, {18, 15}};
  g[{16, 14}] = {{18, 16}, {17, 15}};
  g[{16, 15}] = {{18, 17}};
  g[{16, 16}] = {{17, 17}, {18, 18}};
  g[{16, 18}] = {{18, 19}, {18, 20}};
  g[{17, 18}] = {{19, 18}, {19, 20}};
  g[{18, 0}] = {{19, 2}, {20, 1}, {20, 0}, {19, 0}};
  g[{18, 1}] = {{20, 2}, {19, 1}, {20, 3}};
  g[{18, 2}] = {{19, 3}, {20, 4}};
  g[{18, 3}] = {{20, 5}, {19, 4}};
  g[{18, 4}] = {{20, 6}, {19, 5}};
  g[{18, 5}] = {{20, 7}, {19, 7}};
  g[{18, 6}] = {{19, 6}, {19, 8}};
  g[{18, 7}] = {{20, 9}, {19, 9}};
  g[{18, 8}] = {{20, 8}, {20, 10}};
  g[{18, 9}] = {{19, 10}, {20, 11}};
  g[{18, 10}] = {{20, 12}, {19, 11}};
  g[{18, 11}] = {{19, 12}, {19, 13}};
  g[{18, 12}] = {{20, 13}, {20, 14}, {19, 14}};
  g[{18, 13}] = {{19, 15}, {20, 15}};
  g[{18, 14}] = {{20, 16}, {19, 16}};
  g[{18, 15}] = {{20, 17}, {19, 17}};
  g[{18, 16}] = {{20, 18}};
  g[{18, 17}] = {{19, 19}, {20, 19}};
  g[{18, 18}] = {{20, 20}};
  dfsw(n, g, w, 2, 0);
  dfsw(n, g, w, 2, 1);
  dfsw(n, g, w, 2, 2);
  dfsw(n, g, w, 1, 2);
  dfsw(n, g, w, 0, 2);
  int m = 2 * (n - k - 1);
  if (k == n - 1) {
    // process the tree.
    vector<string> table;
    table.resize(2 * n + 1, string(2 * n + 1, '0'));
    table[0][0] = a[0][0][0];
    table[0][1] = a[0][1][0];
    table[1][0] = a[1][0][0];
    table[1][1] = a[1][1][0];
    int idx = 0;
    dfs(n, g, table, 2, 0, idx, a[2][0]);
    idx = 0;
    dfs(n, g, table, 2, 1, idx, a[2][1]);
    idx = 0;
    dfs(n, g, table, 2, 2, idx, a[2][2]);
    idx = 0;
    dfs(n, g, table, 1, 2, idx, a[1][2]);
    idx = 0;
    dfs(n, g, table, 0, 2, idx, a[0][2]);
    int cccnt = 0;
    vector<vector<bool>> found;
    vector<bool> tmp;
    tmp.resize(2 * n + 1, false);
    found.resize(2 * n + 1, tmp);
    for (int i = 0; i < 2 * n + 1; i++) {
      for (int j = 0; j < 2 * n + 1; j++) {
        if (!found[i][j] && table[i][j] == '1') {
          dfscc(n, found, table, i, j);
          cccnt++;
        }
      }
    }
    string out(100, '0');
    for (int i = 0; i < 30; i++) {
      if (cccnt & (1 << i))
        out[i] = '1';
    }
    return out;
  } else if ((i == m && j <= m) || (i <= m && j == m)) {
    // lift up the information.
    // preorder lifting.
    string s;
    s.push_back(a[0][0][0]);
    for (auto p : g[{i, j}]) {
      string tmp = a[p.first - i][p.second - j];
      for (int l = 0; l <= w[p]; l++) {
        s.push_back(tmp[l]);
      }
    }
    while (s.size() < 100)
      s.push_back('0');
    return s;
  } else {
    return a[0][0];
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11