oj.uz

Submission #893672

# Submission time Handle Problem Language Result Execution time Memory
893672 2023-12-27T09:00:05 Z Darren0724 Monochrome Points (JOI20_monochrome) C++17
4 / 100
 5 ms 3620 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
#define x first
#define y second
const int N=400005;
const int INF=1e18;
const int mod=924844033;
struct BIT{
    vector<int> v=vector<int>(N);
    void add(int p,int t){
        for(int i=p;i<N;i+=i&(-i)){
            v[i]+=t;
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans+=v[i];
        }
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n;cin>>n;
    string s;cin>>s;
    vector<int> a,b;
    for(int i=0;i<n<<1;i++){
        if(s[i]=='W'){
            a.push_back(i+1);
        }
        else{
            b.push_back(i+1);
        }
    }    
    auto solve=[&](int k)->int {
        vector<pair<int,int>> v(n);
        BIT bit;
        for(int i=0;i<n;i++){
            v[i]=make_pair(a[i],b[(i+k)%n]);
            if(v[i].x>v[i].y){
                swap(v[i].x,v[i].y);
            }
            bit.add(v[i].x,1);
            bit.add(v[i].y,-1);
        }
        int ans=0;
        sort(all(v));
        for(int i=0;i<n;i++){
            ans+=bit.ask(v[i].y-1)-bit.ask(v[i].x);
            bit.add(v[i].x,-1);
            bit.add(v[i].y,2);
        }
        return ans;
    };
    int ans=0;
    int l=0,r=n/2+1;
    while(r-l>1){
        int m=(l+r)>>1;
        if(solve(m)>solve(m+1)){
            r=m;
        }
        else{
            l=m;
        }
    }
    ans=max(solve(l),solve(l+1))/2;
    cout<<ans<<endl;

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3500 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3576 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3620 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3500 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3576 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3620 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 5 ms 3620 KB Output is correct
15 Correct 4 ms 3616 KB Output is correct
16 Correct 4 ms 3620 KB Output is correct
17 Correct 4 ms 3620 KB Output is correct
18 Correct 3 ms 3620 KB Output is correct
19 Incorrect 4 ms 3420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3500 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3576 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3620 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 5 ms 3620 KB Output is correct
15 Correct 4 ms 3616 KB Output is correct
16 Correct 4 ms 3620 KB Output is correct
17 Correct 4 ms 3620 KB Output is correct
18 Correct 3 ms 3620 KB Output is correct
19 Incorrect 4 ms 3420 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3500 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 2 ms 3576 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 2 ms 3620 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 5 ms 3620 KB Output is correct
15 Correct 4 ms 3616 KB Output is correct
16 Correct 4 ms 3620 KB Output is correct
17 Correct 4 ms 3620 KB Output is correct
18 Correct 3 ms 3620 KB Output is correct
19 Incorrect 4 ms 3420 KB Output isn't correct
20 Halted 0 ms 0 KB -