Submission #1089567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089567		Error42	Trobojnica (COCI19_trobojnica)	C++17	110 / 110	41 ms	18772 KiB

trobojnica

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

using namespace std;

struct node {
    int color;
    int lower;
    node* prev;
    node* next;
};

struct diagonal {
    int a, b, color;
};

int set_operation(int const x, int const y) {
    return (6 - x - y) % 3;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<node> nodes(n);
    vector<node*> next_different;

    array<int, 3> cnts = { 0, 0, 0 };

    for (int i = 0; i < n; i++) {
        nodes[i].color = (s[i] - '0') % 3;
        nodes[i].lower = i;

        cnts[nodes[i].color]++;

        nodes[i].prev = &nodes[i > 0 ? i - 1 : n - 1];
        nodes[i].next = &nodes[i + 1 < n ? i + 1 : 0];

        next_different.push_back(&nodes[i]);
    }

    if (count(cnts.begin(), cnts.end(), n) || cnts[0] % 2 != n % 2 || cnts[1] % 2 != n % 2 || cnts[2] % 2 != n % 2) {
        cout << "NE\n";
        return 0;
    }

    int node_cnt = n;

    vector<diagonal> diagonals;

    while (node_cnt > 3) {
        int next_different_idx = next_different.size() - 1;

        while (true) {
            node* const cur = next_different[next_different_idx];
            node* const next = cur->next;

            if (cur->color == next->color) {
                next_different.erase(next_different.begin() + next_different_idx);
                next_different_idx--;
                continue;
            }

            if (cnts[cur->color] == 1 && cnts[next->color] == 1) {
                next_different_idx--;
                continue;
            }

            break;
        }

        node* const b = next_different[next_different_idx];
        node* const a = b->prev;
        node* const c = b->next;
        node* const d = c->next;

        int const diag_color = set_operation(b->color, c->color);

        diagonals.push_back({ b->lower, d->lower, diag_color });
        cnts[b->color]--;
        cnts[c->color]--;
        cnts[diag_color]++;

        b->color = diag_color;
        b->next = d;
        d->prev = b;

        next_different.push_back(a);
        next_different.push_back(b);

        node_cnt--;
    }

    cout << "DA\n";

    for (auto const& [a, b, c] : diagonals) {
        cout << a + 1 << " " << b + 1 << " " << (c == 0 ? 3 : c) << "\n";
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50