Submission #992371

#	Time	Username	Problem	Language	Result	Execution time	Memory
992371		onbert	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	600 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
#define int long long

int add (int l, int r) {
    return (l+r)*(r-l+1)/2;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = '.' + s;
    // vector<int> x, y;
    // for (int i=1;i<=2*n;i++) {
    //     if (s[i]=='A') x.push_back(i);
    //     else y.push_back(i);
    // }
    // for (int i:x) cout << i << " "; cout << endl;
    // for (int i:y) cout << i << " "; cout << endl;
    int ans = 0, cnt = 0;
    for (int i=1;i<=2*n;i++) {
        bool change = false;
        if (s[i]=='A') cnt++;
        else cnt--;
        if (s[i]=='B' && cnt<0) {
            int pos = i;
            while (s[pos]=='B') pos++;
            for (int j=pos;j>i;j--) {
                swap(s[j-1], s[j]);
                ans++;
            }
            cnt += 2;
        }
    }
    // cout << s << " " << ans << endl;
    while (true) {
        // cout << "test " << s << endl;
        vector<int> A = {-1}, B = {-1};
        for (int i=1;i<=2*n;i++) {
            if (s[i]=='A') A.push_back(i);
            else B.push_back(i);
        }
        int sum[2*n+1];
        sum[0] = 0;
        for (int i=1;i<=2*n;i++) sum[i] = sum[i-1] + (s[i]=='A');
        vector<pair<int,int>> v;
        int pos = 1;
        while (pos<=n) {
            int cost = sum[B[pos]] - (pos-1);
            v.push_back({cost, B[pos]});
            // cout << pos << " " << cost << endl;
            pos += cost;
        }
        int sz = v.size();
        // cout << sz << endl;
        // for (auto [x, y]:v) cout << x << " " << y << endl;
        if (sz<=k) break;
        int Asum[n+1];
        Asum[0] = 0;
        for (int i=1;i<=n;i++) Asum[i] = A[i] + Asum[i-1];
        int mn = 1e18;
        for (int i=0;i<sz-1;i++) {
            int l = upper_bound(A.begin(), A.end(), v[i].second) - A.begin();
            int r = l + v[i+1].first - 1;
            mn = min((Asum[r]-Asum[l-1]) - add(v[i].second, v[i].second + v[i+1].first - 1), mn);
            // cout << "test " << l << " " << r << endl;
            // cout << Asum[r]-Asum[l-1] << " " << add(v[i].second, v[i].second + v[i+1].first - 1) << endl;
        }
        ans += mn;
        // cout << mn << endl;
        for (int i=0;i<sz-1;i++) {
            int l = upper_bound(A.begin(), A.end(), v[i].second) - A.begin();
            int r = l + v[i+1].first - 1;
            int cur = (Asum[r]-Asum[l-1]) - add(v[i].second, v[i].second + v[i+1].first - 1);
            if (cur==mn) {
                for (int j=l;j<=r;j++) s[A[j]] = 'B';
                // cout << v[i].second << endl;
                for (int j=v[i].second;j<=v[i].second + v[i+1].first - 1;j++) s[j] = 'A';
                break;
            }
        }
        // cout << s << endl;
    }
    cout << ans << endl;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:25:14: warning: unused variable 'change' [-Wunused-variable]
   25 |         bool change = false;
      |              ^~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13