제출 #1311548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311548		Zbyszek99	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	632 ms	5280 KiB

monochrome

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

string move(string s, int x)
{
    string s2;
    int n = siz(s);
    for(int i = n-x; i < n; i++) s2 += s[i];
    rep(i,n-x) s2 += s[i];
    return s2;
}

ll solve(vi& x, vi& y)
{
    if(siz(x) > siz(y)) 
    {
        swap(x,y);
        reverse(all(x));
        reverse(all(y));
    }
    ll cnt0 = 0;
    ll cnt1 = 0;
    ll cnt20 = 0;
    ll cnt21 = 0;
    ll cnty0 = 0;
    ll cnty1 = 0;
    forall(it,x) if(it == 0) cnt0++; else cnt1++;
    forall(it,y) if(it == 0) cnt20++; else cnt21++;
    forall(it,y) if(it == 0) cnty0++; else cnty1++;
    ll ans = siz(x)+(cnt0*(cnt0-1))/2+(cnt1*(cnt1-1))/2;
    int pref0 = -1;
    int pref1 = siz(y)+1;
    int in0 = cnty0-cnt1;
    int in1 = cnty1-cnt0;
    cnty0 = cnty0-cnt1;
    cnty1 = cnt0+1;
    ans += cnty0*(cnty0-1)/2;
    rep(i,siz(y))
    {
        if(y[i] == 0) cnty0--;
        else cnty1--;
        if(cnty0 == 0 && y[i] == 0)
        {
            cnty0--;
            pref0 = i;
        }
        if(cnty1 == 0 && y[i] == 1)
        {
            cnty1--;
            pref1 = i;
        }
    }
    if(pref0 > pref1) return -1;
    int cur_seg = 0;
    rep(i,siz(y))
    {
        if(y[i] == 0)
        {
            if(i <= pref0) cur_seg++;
            else ans += cur_seg;
        }
        else
        {
            if(i >= pref1) cur_seg--;
            else ans += cur_seg;
        }
    }
    int up1 = cnt1;
    int down0 = cnt20-in1;
    int cur_ptr = -1;
    rep(i,siz(x))
    {
        if(x[i] == 1)
        {
            up1--;
            continue;
        }
        cur_ptr++;
        while(y[cur_ptr] == 0)
        {
            if(cur_ptr > pref0) down0--;
            cur_ptr++;
        }
        ans += min(up1,down0);
    }
    int up0 = cnt0;
    int down1 = cnt21-in0;
    cur_ptr = -1;
    rep(i,siz(x))
    {
        if(x[i] == 0)
        {
            up0--;
            continue;
        }
        cur_ptr++;
        while(y[cur_ptr] == 1 || cur_ptr <= pref0)
        {
            if(cur_ptr < pref1 && y[cur_ptr] == 1) down1--;
            cur_ptr++;
        }
        ans += min(up0,down1);
    }
    return ans;
}

int n;
string s;
ll ans = 0;

ll check_ind(int k)
{
    vi x,y;
    rep2(j,1,k-1) if(s[j] == 'W') x.pb(0); else x.pb(1);
    rep2(j,k+1,n-1) if(s[j] == 'W') y.pb(0); else y.pb(1);
    ll ans2 = solve(x,y);
    ans = max(ans,ans2);
    return ans2;
}

bool check_dir(vi& V, int ind)
{
    bool dir = 0;
    ll val1 = check_ind(V[ind]);
    rep2(ind2,ind+1,siz(V)-1)
    {
        ll val2 = check_ind(V[ind2]);
        if(val2 == val1) continue;
        if(val2 > val1) dir = 1;
        break;
    }
    return dir;
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cerr.tie(0);
    //random_start();
    cin >> n >> s;
    n *= 2;
    int d = 0;
    rep(i,n) if(s[i] == 'W') d = n-i;
    s = move(s,d);
    int mid = n/2;
    vi V;
    rep(i,n) if(s[i] == 'B') V.pb(i);
    int mid_point = 0;
    rep(i,siz(V)) if(V[i] < n/2) mid_point = i;
    int l = 0;
    int r = mid_point;
    int l_bor = mid_point+1;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check_ind(V[mid]) != -1)
        {
            l_bor = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    l = mid_point+1;
    r = siz(V)-1;
    int r_bor = mid_point;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check_ind(V[mid]) != -1)
        {
            r_bor = mid;
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    l = l_bor;
    r = r_bor;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check_dir(V,mid))
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    cout << ans << '\n';
}

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