Submission #1141077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141077		the_coding_pooh	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	1905 ms	4116 KiB

monochrome

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

#define fs first
#define sc second

const int SIZE = 2e5 + 5;
const double TL1 = 1, TL2 = 1.9;

string S;

int pos[2][SIZE], seg[SIZE];

int BITree[SIZE];

void modify(int pos, int val){
    for (; pos < SIZE; pos += (pos & - pos)){
        BITree[pos] += val;
    }
    return;
}

int query(int pos){
    int ret = 0;
    for (; pos; pos -= (pos & - pos)){
        ret += BITree[pos];
    }
    return ret;
}

#define is_W(i) (S[(i + x) % (2 * N)] == 'W')

long long vv[2 * SIZE];

long long eval(int x, int N){
    if(x < 0 || x >= 2 * N)
        return 0;
    if(vv[x])
        return vv[x];
    for (int i = 0; i < 2 * N; i++){
        BITree[i] = 0;
    }
    int ptr[2] = {0, 0};
    for (int i = N; i < S.size(); i++){
        pos[is_W(i)][ptr[is_W(i)]++] = i;
    }
    ptr[0] = 0, ptr[1] = 0;
    for (int i = 0; i < N; i++){
        vv[x] += query(pos[1 - is_W(i)][ptr[1 - is_W(i)]]);
        modify(pos[1 - is_W(i)][ptr[1 - is_W(i)]++], 1);
    }
    return vv[x];
}

mt19937 rng(time(0));

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N;
    cin >> N >> S;
    long long ans = 0, mx = 0;
    auto ck = clock();
    for (; double(clock() - ck) / CLOCKS_PER_SEC < TL1;){
        int p = rng() % (2 * N);
        if(eval(p, N) > ans){
            ans = eval(p, N);
            mx = p;
        }
    }
    for (int i = 1; double(clock() - ck) / CLOCKS_PER_SEC < TL2; i++){
        ans = max({ans, eval(mx + i, N), eval(mx - i, N)});
    }
    cout << ans << '\n';
    uwu
}

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