oj.uz

Submission #992371

# Submission time Handle Problem Language Result Execution time Memory
992371 2024-06-04T10:43:59 Z onbert Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 600 KB 
#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

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -