#include <bits/stdc++.h>
using namespace std;
struct node {
node *col, *l, *r, *u, *d;
int row, size;
};
void cover(node* c) {
c->r->l = c->l;
c->l->r = c->r;
for (node* i = c->d; i != c; i = i->d) {
for (node* j = i->r; j != i; j = j->r) {
j->d->u = j->u;
j->u->d = j->d;
j->col->size--;
}
}
}
void uncover(node* c) {
for (node* i = c->u; i != c; i = i->u) {
for (node* j = i->l; j != i; j = j->l) {
j->col->size++;
j->d->u = j;
j->u->d = j;
}
}
c->r->l = c;
c->l->r = c;
}
int tries = 0;
bool search(int k, node* head, vector<node*>& answer) {
if (head->r == head) return true; // 모든 column을 다 cover했을 때
if (tries > 200000) return false;
tries++;
node* c = 0; int low = INT_MAX;
for (node* i = head->r; i != head; i = i->r) {
if (i->size < low) {
if (i->size == 0)
return false;
low = i->size; c = i;
}
}
cover(c);
for (node* i = c->d; i != c; i = i->d) {
answer.push_back(i);
for (node* j = i->r; j != i; j = j->r) {
cover(j->col);
}
if (search(k + 1, head, answer)) {
return true;
} else {
for (node* j = i->l; j != i; j = j->l) {
uncover(j->col);
}
answer.pop_back();
}
}
uncover(c);
return false;
}
node* build(vector<vector<int>> matrix) {
int n = matrix.size(), m = matrix[0].size();
node* head = new node();
vector<node*> column(m);
for (int i = 0; i < m; ++i) column[i] = new node();
for (int i = 0; i < m; ++i) {
column[i]->col = column[i]->u = column[i]->d = column[i];
if (i == 0) column[i]->l = head, head->r = column[i];
else column[i]->l = column[i - 1];
if (i == m - 1) column[i]->r = head, head->l = column[i];
else column[i]->r = column[i + 1];
}
for (int i = 0; i < n; ++i) {
node* prev = 0;
for (int j = 0; j < m; ++j) {
if (matrix[i][j] == 0) continue;
node* cur = new node();
cur->row = i;
cur->col = column[j];
cur->u = column[j]->u; cur->d = column[j];
if (prev) {
cur->l = prev; cur->r = prev->r;
prev->r->l = cur; prev->r = cur;
} else {
cur->l = cur->r = cur;
}
column[j]->u->d = cur; column[j]->u = cur;
column[j]->size++;
prev = cur;
}
}
return head;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N; cin >> N;
int max_len = 4 * N - 1;
vector<vector<int>> mp(N * 2, vector<int>(max_len, -1));
vector<vector<bool>> is_upper(N * 2, vector<bool>(max_len, false));
for (int i = 0; i < N * 2; ++i) {
string s; cin >> s;
bool flag = i < N;
int offset = (max_len - s.size()) / 2;
for (int j = 0; j < s.size(); ++j) {
if (s[j] == '0') {
mp[i][offset + j] = 0;
} else {
mp[i][offset + j] = -1;
}
is_upper[i][offset + j] = flag;
flag ^= 1;
}
}
// test
// for (int i = 0; i < N * 2; ++i) {
// for (int j = 0; j < max_len; ++j) {
// cout << mp[i][j] << " ";
// }
// cout << endl;
// }
// 행 구성 요소
// rectangle: 각 칸에는 하나의 색깔만 채울 수 있다
// rectangle * 6 => 각 칸에 대해 6가지 가능한 색깔
vector<vector<int>> matrix;
const int colors = 6, rectangle = (N * 2) * max_len, row_size = rectangle * (colors + 1);
// i, j: 시작 좌표
// k: 색깔
// d : 방향
// 0) 수평 방향
// 1) 아래쪽 -> 오른쪽 (is_upper == true)
// 2) 오른쪽 -> 위쪽 (is_upper == true)
// 3) 오른쪽 -> 아래쪽 (is_upper == false)
// 4) 위쭉 -> 오른쪽 (is_upper == false)
vector<tuple<int, int, int, int>> info;
auto new_row = [&]() -> vector<int>& {
matrix.emplace_back(row_size, 0);
return matrix.back();
};
auto coord = [&](int i, int j) -> int {
return i * max_len * colors + j * colors;
};
auto is_valid = [&](int i, int j) -> bool {
return i >= 0 && i < N * 2 && j >= 0 && j < max_len && mp[i][j] != -1;
};
auto set_row = [&](vector<int>& row, int i, int j, int k, bool take = true) {
if (take) row[i * max_len + j] = 1;
row[coord(i, j) + k + rectangle] = 1;
};
auto set_if_valid = [&](vector<int>& row, int i, int j, int k) {
if (is_valid(i, j)) set_row(row, i, j, k, false);
};
for (int i = 0; i < N * 2; ++i) {
for (int j = 0; j < max_len; ++j) {
if (!is_valid(i, j)) {
// 아무것도 안채우는 경우
auto& row = new_row();
set_row(row, i, j, 0); set_row(row, i, j, 1); set_row(row, i, j, 2);
set_row(row, i, j, 3); set_row(row, i, j, 4); set_row(row, i, j, 5);
info.emplace_back(i, j, -1, -1);
} else {
for (int k = 0; k < colors; ++k) {
// 수평 방향
if (is_valid(i, j + 1) && is_valid(i, j + 2)) {
auto& row = new_row();
set_row(row, i, j, k);
set_row(row, i, j + 1, k);
set_row(row, i, j + 2, k);
if (is_upper[i][j]) {
set_if_valid(row, i + 1, j, k);
set_if_valid(row, i - 1, j + 1, k);
set_if_valid(row, i + 1, j + 2, k);
} else {
set_if_valid(row, i - 1, j, k);
set_if_valid(row, i + 1, j + 1, k);
set_if_valid(row, i - 1, j + 2, k);
}
set_if_valid(row, i, j - 1, k);
set_if_valid(row, i, j + 3, k);
info.emplace_back(i, j, k, 0);
}
// 아래쪽 -> 오른쪽
if (is_upper[i][j] && is_valid(i + 1, j) && is_valid(i + 1, j + 1)) {
auto& row = new_row();
set_row(row, i, j, k);
set_row(row, i + 1, j, k);
set_row(row, i + 1, j + 1, k);
set_if_valid(row, i, j - 1, k);
set_if_valid(row, i, j + 1, k);
set_if_valid(row, i + 1, j - 1, k);
set_if_valid(row, i + 1, j + 2, k);
set_if_valid(row, i + 2, j + 1, k);
info.emplace_back(i, j, k, 1);
}
// 오른쪽 -> 위쪽
if (is_upper[i][j] && is_valid(i, j + 1) && is_valid(i - 1, j + 1)) {
auto& row = new_row();
set_row(row, i, j, k);
set_row(row, i, j + 1, k);
set_row(row, i - 1, j + 1, k);
set_if_valid(row, i, j - 1, k);
set_if_valid(row, i + 1, j, k);
set_if_valid(row, i, j + 2, k);
set_if_valid(row, i - 1, j, k);
set_if_valid(row, i - 1, j + 2, k);
info.emplace_back(i, j, k, 2);
}
// 오른쪽 -> 아래쪽
if (!is_upper[i][j] && is_valid(i, j + 1) && is_valid(i + 1, j + 1)) {
auto& row = new_row();
set_row(row, i, j, k);
set_row(row, i, j + 1, k);
set_row(row, i + 1, j + 1, k);
set_if_valid(row, i - 1, j, k);
set_if_valid(row, i, j - 1, k);
set_if_valid(row, i, j + 2, k);
set_if_valid(row, i + 1, j, k);
set_if_valid(row, i + 1, j + 2, k);
info.emplace_back(i, j, k, 3);
}
// 위쪽 -> 오른쪽
if (!is_upper[i][j] && is_valid(i - 1, j) && is_valid(i - 1, j + 1)) {
auto& row = new_row();
set_row(row, i, j, k);
set_row(row, i - 1, j, k);
set_row(row, i - 1, j + 1, k);
set_if_valid(row, i, j - 1, k);
set_if_valid(row, i, j + 1, k);
set_if_valid(row, i - 1, j - 1, k);
set_if_valid(row, i - 1, j + 2, k);
set_if_valid(row, i - 2, j + 1, k);
info.emplace_back(i, j, k, 4);
}
}
}
}
}
// dummy rows for each colors
for (int i = 0; i < N * 2; ++i) {
for (int j = 0; j < max_len; ++j) {
if (mp[i][j] == -1) continue;
for (int k = 0; k < colors; ++k) {
auto& row = new_row();
set_row(row, i, j, k, false);
info.emplace_back(i, j, k, -1);
}
}
}
node* head = build(matrix);
vector<node*> answer;
bool found = search(0, head, answer);
if (!found) {
cout << "nemoguce" << endl;
return 0;
}
for (auto& nd : answer) {
auto& [i, j, k, d] = info[nd->row];
if (d == -1) {
// mp[i][j] = k + 1;
} else if (d == 0) {
mp[i][j] = mp[i][j + 1] = mp[i][j + 2] = k + 1;
} else if (d == 1) {
mp[i][j] = mp[i + 1][j] = mp[i + 1][j + 1] = k + 1;
} else if (d == 2) {
mp[i][j] = mp[i][j + 1] = mp[i - 1][j + 1] = k + 1;
} else if (d == 3) {
mp[i][j] = mp[i][j + 1] = mp[i + 1][j + 1] = k + 1;
} else if (d == 4) {
mp[i][j] = mp[i - 1][j] = mp[i - 1][j + 1] = k + 1;
} else assert(0);
}
for (int i = 0; i < N * 2; ++i) {
int offset = i < N ? (N - i - 1) : (i - N);
for (int j = offset; j < max_len - offset; ++j) {
if (mp[i][j] == -1) cout << ".";
else cout << mp[i][j];
}
cout << endl;
}
return 0;
}
Compilation message
trapezi.cpp: In function 'int main()':
trapezi.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int j = 0; j < s.size(); ++j) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1360 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 3 |
Correct |
1 ms |
848 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4176 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2896 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1872 KB |
Output is correct |
| 4 |
Correct |
4 ms |
4176 KB |
Output is correct |
| 5 |
Correct |
69 ms |
3408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12880 KB |
Output is correct |
| 2 |
Correct |
100 ms |
13136 KB |
Output is correct |
| 3 |
Correct |
9 ms |
10832 KB |
Output is correct |
| 4 |
Incorrect |
69 ms |
9296 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
36424 KB |
Output is correct |
| 2 |
Correct |
26 ms |
32848 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14160 KB |
Output is correct |
| 4 |
Correct |
24 ms |
31056 KB |
Output is correct |
| 5 |
Incorrect |
335 ms |
31548 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
