Submission #1140478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140478		browntoad	Monochrome Points (JOI20_monochrome)	C++20	25 / 100	5 ms	1864 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const ll maxn = 2e5+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;

int n;
vector<int> bit(maxn);
int quer(int a){
    int ret = 0;
    while(a > 0){
        ret += bit[a];
        a -= (a&-a);
    }
    return ret;
}
void modify(int a){
    while(a <= n){
        bit[a]++;
        a += (a&-a);
    }
}


int run(string str){
    REP1(i, n) bit[i] = 0;
    vector<int> bs, ws;
    REP(i, n){
        if (str[i] == 'B') bs.pb(i+1); // 1-base
        else ws.pb(i+1);
    }
    int bptr = 0, wptr = 0;

    vector<int> ret(n);
    FOR(i, n, 2*n){
        if (str[i] == 'B') ret[i-n] = ws[wptr++];
        else ret[i-n] = bs[bptr++];
    }

    int ans = 0;
    REP(i, n){
        ans += quer(ret[i]);
        modify(ret[i]);
    }
    return ans;
}
signed main(){
    IOS();
    cin>>n;
    string str; cin>>str;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int ans = 0;
    REP(t, 60){
        ans = max(ans, run(str));
        if (rng()%4 == 0){
            reverse(ALL(str));
        }
        else {
            int pp = rng()%(2*n);
            string tmp = str.substr(0, pp);
            str.erase(str.begin(), str.begin()+pp);
            str += tmp;
        }
    }
    cout<<ans<<endl;
}

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