Submission #869981

#	Time	Username	Problem	Language	Result	Execution time	Memory
869981		green_gold_dog	Monochrome Points (JOI20_monochrome)	C++17	4 / 100	28 ms	468 KiB

monochrome

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

set<pair<ll, ll>> bw, rbw, wb, rwb;

void e(ll l, ll r) {
        bw.erase(make_pair(l, r));
        rbw.erase(make_pair(r, l));
        wb.erase(make_pair(l, r));
        rwb.erase(make_pair(r, l));
}

void iwb(ll l, ll r);

void ibw(ll l, ll r) {
        if (r < l) {
                iwb(r, l);
                return;
        }
        auto it = bw.lower_bound(make_pair(l, r));
        if (it != bw.end() && it->second < r) {
                auto[nl, nr] = *it;
                e(nl, nr);
                ibw(l, nr);
                ibw(nl, r);
                return;
        }
        if (it != bw.begin()) {
                it--;
                if (it->second > r) {
                        auto[nl, nr] = *it;
                        e(nl, nr);
                        ibw(l, nr);
                        ibw(nl, r);
                        return;
                }
        }
        it = wb.lower_bound(make_pair(r, 0));
        if (it != wb.end()) {
                auto[nl, nr] = *it;
                e(nl, nr);
                ibw(l, nl);
                iwb(r, nr);
                return;
        }
        it = rwb.lower_bound(make_pair(l, 0));
        if (it != rwb.begin()) {
                it--;
                auto[nr, nl] = *it;
                e(nl, nr);
                ibw(nr, r);
                iwb(nl, l);
                return;
        }
        bw.insert(make_pair(l, r));
        rbw.insert(make_pair(r, l));
}

void iwb(ll l, ll r) {
        if (r < l) {
                ibw(r, l);
                return;
        }
        auto it = wb.lower_bound(make_pair(l, r));
        if (it != wb.end() && it->second < r) {
                auto[nl, nr] = *it;
                e(nl, nr);
                iwb(l, nr);
                iwb(nl, r);
                return;
        }
        if (it != wb.begin()) {
                it--;
                if (it->second > r) {
                        auto[nl, nr] = *it;
                        e(nl, nr);
                        iwb(l, nr);
                        iwb(nl, r);
                        return;
                }
        }
        it = bw.lower_bound(make_pair(r, 0));
        if (it != bw.end()) {
                auto[nl, nr] = *it;
                e(nl, nr);
                iwb(l, nl);
                ibw(r, nr);
                return;
        }
        it = rbw.lower_bound(make_pair(l, 0));
        if (it != rbw.begin()) {
                it--;
                auto[nr, nl] = *it;
                e(nl, nr);
                iwb(nr, r);
                ibw(nl, l);
                return;
        }
        wb.insert(make_pair(l, r));
        rwb.insert(make_pair(r, l));
}

bool trybw(bool b = false) {
        if (bw.size() < 2) {
                return false;
        }
        auto[l1, r1] = *bw.begin();
        auto[r2, l2] = *rbw.rbegin();
        e(l1, r1);
        e(l2, r2);
        if (r1 < l2) {
                ll ml = -1, mr = -1;
                for (auto[nl, nr] : bw) {
                        if (nl > r1 || nr < l2) {
                                ml = nl;
                                mr = nr;
                                break;
                        }
                }
                if (ml != -1) {
                        e(ml, mr);
                        swap(r1, mr);
                        swap(mr, r2);
                        ibw(l1, r1);
                        ibw(l2, r2);
                        ibw(ml, mr);
                        return true;
                }
                if (b) {
                        swap(r1, r2);
                        ibw(l1, r1);
                        ibw(l2, r2);
                        return true;
                }
        }
        ibw(l1, r1);
        ibw(l2, r2);
        return false;
}

bool trywb(bool b = false) {
        if (wb.size() < 2) {
                return false;
        }
        auto[l1, r1] = *wb.begin();
        auto[r2, l2] = *rwb.rbegin();
        e(l1, r1);
        e(l2, r2);
        if (r1 < l2) {
                ll ml = -1, mr = -1;
                for (auto[nl, nr] : wb) {
                        if (nl > r1 || nr < l2) {
                                ml = nl;
                                mr = nr;
                                break;
                        }
                }
                if (ml != -1) {
                        e(ml, mr);
                        swap(r1, mr);
                        swap(mr, r2);
                        iwb(l1, r1);
                        iwb(l2, r2);
                        iwb(ml, mr);
                        return true;
                }
                if (b) {
                        swap(r1, r2);
                        iwb(l1, r1);
                        iwb(l2, r2);
                        return true;
                }
        }
        iwb(l1, r1);
        iwb(l2, r2);
        return false;
}

ll count() {
        vector<pair<ll, ll>> all;
        for (auto i : wb) {
                all.push_back(i);
        }
        for (auto i : bw) {
                all.push_back(i);
        }
        ll ans = 0;
        for (auto[l, r] : all) {
                for (auto[nl, nr] : all) {
                        if ((nr > r) && (nl < r) && (nl > l)) {
                                ans++;
                        }
                }
        }
        return ans;
}

void solve() {
        ll n;
        cin >> n;
        string s;
        cin >> s;
        vector<ll> b, w;
        for (ll i = 0; i < n * 2; i++) {
                if (s[i] == 'B') {
                        b.push_back(i);
                } else {
                        w.push_back(i);
                }
        }
        for (ll i = 0; i < n; i++) {
                ibw(b[i], w[i]);
        }
        ll ans = 0, x = 1;
        bool bb = false;
        while (x || trybw() || trywb()) {
                x = 0;
                assign_max(ans, count());
                if (bb) {
                        trybw(true);
                } else {
                        trywb(true);
                }
                bb = !bb;
                assign_max(ans, count());
        }
        cout << ans << '\n';
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:278:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  278 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
monochrome.cpp:279:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  279 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65