#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";
}
}
# |
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 |
# |
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 |
# |
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 |