| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572646 |
2022-06-04T22:28:06 Z |
Plurm |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
320 KB |
#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 (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];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
