oj.uz

Submission #1089567

# Submission time Handle Problem Language Result Execution time Memory
1089567 2024-09-16T16:48:14 Z Error42 Trobojnica (COCI19_trobojnica) C++17
110 / 110
 41 ms 18772 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 });
        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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 41 ms 18772 KB Output is correct
22 Correct 39 ms 16904 KB Output is correct
23 Correct 0 ms 600 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 39 ms 14036 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 19 ms 6928 KB Output is correct
28 Correct 4 ms 7512 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 5 ms 7516 KB Output is correct