This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 2e5 + 5;
int n;
string s;
set<tuple<int, int, int>> st;
set<pair<int, int>> p[4];
vector<tuple<int, int, int>> ans;
bool in(int i) {
auto it = st.lower_bound({i, 0, 0});
return it != st.end() && get<0>(*it) == i;
}
int color(int i) {
auto it = st.lower_bound({i, 0, 0});
return get<2>(*it);
}
void connect(int l, int r) {
auto lit = st.lower_bound({l, 0, 0});
auto [l1, r1, c1] = *lit;
st.erase(lit);
auto rit = st.lower_bound({r, 0, 0});
auto [l2, r2, c2] = *rit;
st.erase(rit);
ans.pb(l1, r2, 6 - c1 - c2);
st.emplace(l1, r2, 6 - c1 - c2);
auto it = st.lower_bound({l1, 0, 0});
if (it != st.begin()) lit = prev(it);
else lit = --st.end();
if (it != --st.end()) rit = next(it);
else rit = st.begin();
tie(l1, r1, c1) = *lit;
tie(l2, r2, c2) = *it;
if (c1 != c2) p[6 - c1 - c2].emplace(l1, r1);
tie(l1, r1, c1) = *it;
tie(l2, r2, c2) = *rit;
if (c1 != c2) p[6 - c1 - c2].emplace(l1, r1);
}
void solve() {
cin >> n >> s;
s = " " + s;
int cnt[4] = {};
FOR (i, 1, n) cnt[s[i] - '0']++;
FOR (i, 1, 3) {
int x = n - 3 - cnt[i];
if (x % 2 == 0) {
cout << "NE\n";
return;
}
x = (x + 1) / 2;
if (x < 0) {
cout << "NE\n";
return;
}
cnt[i] = x;
}
FOR (i, 1, n) {
st.emplace(i, i % n + 1, s[i] - '0');
if (s[i] != s[i % n + 1]) p[6 - (s[i] - '0') - (s[i % n + 1] - '0')].emplace(i, i % n + 1);
}
while (st.size() > 3) {
bool ok = 0;
while (ok == 0) {
ok = 1;
int l = 0, r = 0, ii = 0;
FOR (i, 1, 3) if (cnt[i] && p[i].size()) {
tie(l, r) = *p[i].begin();
p[i].erase(p[i].begin());
ii = i;
break;
}
if (!in(l) || !in(r)) {
ok = 0;
continue;
}
int cl = color(l), cr = color(r);
if (cl == cr || 6 - cl - cr != ii) {
ok = 0;
continue;
}
cnt[ii]--;
connect(l, r);
}
}
cout << "DA\n";
for (auto [a, b, c] : ans) cout << a << ' ' << b << ' ' << c << '\n';
}
int main() {
Waimai;
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |