# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
910967 | 2024-01-18T10:22:16 Z | CyberCow | Trobojnica (COCI19_trobojnica) | C++17 | 0 ms | 0 KB |
#include <random> #include <algorithm> #include <bitset> #include <chrono> #include <cmath> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include <chrono> #define fr first #define sc second #define ad push_back using namespace std; using ll = long long; mt19937 rnd(348502); const ll N = 200005; pair<int, int> gn[N]; int abc[5]; void solve() { int n, i, j, x, y; cin >> n; char cc; int a = 0, b = 0, c = 0; vector<int> v; for ( i = 0; i < n; i++) { cin >> cc; if (cc == '1') { a++; v.push_back(1); abc[1]++; } else if (cc == '2') { b++; v.push_back(2); abc[2]++; } else { c++; v.push_back(3); abc[3]++; } } if (max(a, max(b, c)) == n || a % 2 != b % 2 || a % 2 != c % 2 || b % 2 != c % 2) { cout << "NE\n"; return; } for ( i = 0; i < n - 1; i++) { gn[i + 1] = { i + 2, v[i] }; } gn[n] = { 1, v[n - 1] }; int qan = 0, gag = 1; vector<pair<int, pair<int, int>>> ans; while (qan < n - 3) { while (gn[gag].second == gn[gn[gag].first].second || !(abc[gn[gag].second] == max(a, max(b, c)) || abc[gn[gn[gag].first].second] == max(a, max(b, c)))) { gag = gn[gag].first; } qan++; if (gn[gag].second != 1 && gn[gn[gag].first].second != 1) { ans.push_back({ 1, {gag, gn[gn[gag].first].first} }); a++; b--; c--; abc[1]++; abc[2]--; abc[3]--; gn[gag].second = 1; gn[gag].first = gn[gn[gag].first].first; continue; } if (gn[gag].second != 2 && gn[gn[gag].first].second != 2) { ans.push_back({ 2, {gag, gn[gn[gag].first].first} }); a--; b++; c--; abc[1]--; abc[2]++; abc[3]--; gn[gag].second = 2; gn[gag].first = gn[gn[gag].first].first; continue; } if (gn[gag].second != 3 && gn[gn[gag].first].second != 3) { ans.push_back({ 3, {gag, gn[gn[gag].first].first} }); a--; b--; c++; abc[1]--; abc[2]--; abc[3]++; gn[gag].second = 3; gn[gag].first = gn[gn[gag].first].first; continue; } } cout << "DA\n"; for ( i = 0; i < ans.size(); i++) { cout << ans[i].second.first << ' ' << ans[i].second.second << ' ' << ans[i].first << '\n'; } }