#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 > 2000000) 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;
}
}
// 행 구성 요소
// rectangle: 각 칸에는 하나의 색깔만 채울 수 있다
// rectangle * 6 => 각 칸에 대해 6가지 가능한 색깔
vector<vector<int>> matrix; matrix.reserve(5'000);
const int rectangle = (N * 2) * max_len;
// 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>> info;
auto new_row = [&]() -> vector<int>& {
matrix.emplace_back(rectangle, 0);
return matrix.back();
};
auto coord = [&](int i, int j) -> int {
return i * max_len + j;
};
auto in_range = [&](int i, int j) -> bool {
return i >= 0 && i < N * 2 && j >= 0 && j < max_len;
};
auto is_valid = [&](int i, int j) -> bool {
return in_range(i, j) && mp[i][j] != -1;
};
auto set_row = [&](vector<int>& row, int i, int j) {
row[coord(i, j)] = 1;
};
vector<int>& blank_row = new_row();
info.emplace_back(-1, -1, -1);
for (int i = 0; i < N * 2; ++i) {
for (int j = 0; j < max_len; ++j) {
if (!is_valid(i, j)) {
// 아무것도 안채우는 경우
set_row(blank_row, i, j);
} else {
if (is_valid(i, j + 1) && is_valid(i, j + 2)) {
auto& row = new_row();
set_row(row, i, j); set_row(row, i, j + 1); set_row(row, i, j + 2);
info.emplace_back(i, j, 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); set_row(row, i + 1, j); set_row(row, i + 1, j + 1);
info.emplace_back(i, j, 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); set_row(row, i, j + 1); set_row(row, i - 1, j + 1);
info.emplace_back(i, j, 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); set_row(row, i, j + 1); set_row(row, i + 1, j + 1);
info.emplace_back(i, j, 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); set_row(row, i - 1, j); set_row(row, i - 1, j + 1);
info.emplace_back(i, j, 4);
}
}
}
}
node* head = build(matrix);
vector<node*> answer;
bool found = search(0, head, answer);
if (!found) {
cout << "nemoguce" << endl;
return 0;
}
const set<int> color_pool = {1, 2, 3, 4, 5, 6};
set<int> color;
for (auto& nd : answer) {
auto& [i, j, d] = info[nd->row];
if (d == -1) continue;
color = color_pool;
auto erase_color = [&](int i, int j) {
if (is_valid(i, j)) color.erase(mp[i][j]);
};
// adjacent한 칸에 같은 색깔이 없도록 제거
if (d == 0) {
erase_color(i, j - 1); erase_color(i, j + 3);
if (is_upper[i][j]) {
erase_color(i + 1, j); erase_color(i - 1, j + 1); erase_color(i + 1, j + 2);
} else {
erase_color(i - 1, j); erase_color(i + 1, j + 1); erase_color(i - 1, j + 2);
}
assert(color.size() > 0);
mp[i][j] = mp[i][j + 1] = mp[i][j + 2] = *color.begin();
} else if (d == 1) {
erase_color(i, j - 1); erase_color(i, j + 1);
erase_color(i + 1, j - 1); erase_color(i + 1, j + 2);
erase_color(i + 2, j + 1);
assert(color.size() > 0);
mp[i][j] = mp[i + 1][j] = mp[i + 1][j + 1] = *color.begin();
} else if (d == 2) {
erase_color(i, j - 1); erase_color(i + 1, j);
erase_color(i, j + 2); erase_color(i - 1, j);
erase_color(i - 1, j + 2);
assert(color.size() > 0);
mp[i][j] = mp[i][j + 1] = mp[i - 1][j + 1] = *color.begin();
} else if (d == 3) {
erase_color(i - 1, j); erase_color(i, j - 1);
erase_color(i, j + 2); erase_color(i + 1, j);
erase_color(i + 1, j + 2);
assert(color.size() > 0);
mp[i][j] = mp[i][j + 1] = mp[i + 1][j + 1] = *color.begin();
} else if (d == 4) {
erase_color(i, j - 1); erase_color(i, j + 1);
erase_color(i - 1, j - 1); erase_color(i - 1, j + 2);
erase_color(i - 2, j + 1);
assert(color.size() > 0);
mp[i][j] = mp[i - 1][j] = mp[i - 1][j + 1] = *color.begin();
} 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:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | 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 |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
464 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1104 KB |
Output is correct |
| 2 |
Correct |
1 ms |
848 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
848 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1020 KB |
Output is correct |
| 6 |
Correct |
1 ms |
848 KB |
Output is correct |
| 7 |
Correct |
1 ms |
968 KB |
Output is correct |
| 8 |
Correct |
1 ms |
848 KB |
Output is correct |
| 9 |
Correct |
1 ms |
848 KB |
Output is correct |
| 10 |
Correct |
23 ms |
848 KB |
Output is correct |
