Submission #1106055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106055		tjgus1668	Trapezi (COI17_trapezi)	C++17	23 / 100	1101 ms	36584 KiB

trapezi

#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;
        }
    }

    // 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 (stderr)

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) {
      |                         ~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 22
• Subtask 5: 0 / 37