oj.uz

답안 #704773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704773 2023-03-03T01:51:26 Z becaido Trobojnica (COCI19_trobojnica) C++17
0 / 110
 2000 ms 212 KB 
#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;
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 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;
        }
    }
    FOR (i, 1, n) {
        st.emplace(i, i % n + 1, s[i] - '0');
        if (s[i] != s[i % n + 1]) p.emplace(i, i % n + 1);
    }
    while (st.size() > 3) {
        bool ok = 0;
        while (ok == 0) {
            ok = 1;
            auto [l, r] = *p.begin();
            p.erase(p.begin());
            if (in(l) && in(r) && color(l) != color(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.emplace(l1, r1);

                tie(l1, r1, c1) = *it;
                tie(l2, r2, c2) = *rit;
                if (c1 != c2) p.emplace(l1, r1);
            } else {
                ok = 0;
            }
        }
    }
    cout << "DA\n";
    for (auto [a, b, c] : ans) cout << a << ' ' << b << ' ' << c << '\n';
}

int main() {
    Waimai;
    solve();
}

Subtask #1
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -