oj.uz

Submission #1089554

# Submission time Handle Problem Language Result Execution time Memory
1089554 2024-09-16T16:21:23 Z Error42 Trobojnica (COCI19_trobojnica) C++17
0 / 110
 0 ms 348 KB 
#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 });

        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
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -