oj.uz

Submission #487617

# Submission time Handle Problem Language Result Execution time Memory
487617 2021-11-16T09:40:08 Z KazamaHoang Trobojnica (COCI19_trobojnica) C++14
110 / 110
 55 ms 7500 KB 
#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.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 55 ms 7500 KB Output is correct
22 Correct 49 ms 6472 KB Output is correct
23 Correct 0 ms 336 KB Output is correct
24 Correct 0 ms 336 KB Output is correct
25 Correct 52 ms 7380 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 27 ms 3740 KB Output is correct
28 Correct 8 ms 4352 KB Output is correct
29 Correct 0 ms 208 KB Output is correct
30 Correct 5 ms 2000 KB Output is correct