Submission #487617

#	Time	Username	Problem	Language	Result	Execution time	Memory
487617		KazamaHoang	Trobojnica (COCI19_trobojnica)	C++14	110 / 110	55 ms	7500 KiB

trobojnica

#include <bits/stdc++.h>

using namespace std;

int n;
int nxt[200005], col[200005], cnt[4];
set<int> pos;
int ans[200005][3];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        char ch;
        cin >> ch;
        col[i] = ch - '0';
        nxt[i] = (i + 1) % n;
        ++ cnt[col[i]];
    }
    int x = 0;
    for (int i = 0, y; i < n - 3; ++ i) {
        int numCol = (cnt[1] > 0) + (cnt[2] > 0) + (cnt[3] > 0);
        if (numCol == 1) {
            cout << "NE\n";
            return 0;
        }
        while (1) {
            y = nxt[x];
            if (col[x] == col[y]) x = nxt[x];
            else if (cnt[col[x]] == 1 && cnt[col[y]] == 1) x = nxt[x];
            else break;
        }
        -- cnt[col[x]];
        -- cnt[col[y]];
        nxt[x] = nxt[y];
        col[x] = 1 + 2 + 3 - col[x] - col[y];
        ++ cnt[col[x]];
        ans[i][0] = x + 1;
        ans[i][1] = nxt[y] + 1;
        ans[i][2] = col[x];
    }
    if (!cnt[1] || !cnt[2] || !cnt[3]) {
        cout << "NE\n";
        return 0;
    }
    cout << "DA\n";
    for (int i = 0; i < n - 3; ++ i) {
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << "\n";
    }
    return 0;
}

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