oj.uz

Submission #623137

# Submission time Handle Problem Language Result Execution time Memory
623137 2022-08-05T08:53:31 Z Mahdi Monochrome Points (JOI20_monochrome) C++17
4 / 100
 6 ms 724 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2e5+5;
int n, cws[N], cbs[N], cwt[N], cbt[N];
bool g[N], h[N];
     
ll BW(const string &s, const string &t){
    int m=s.size();
    vector<int>ws, bs, wt, bt;
    for(int i=1;i<=m;++i){
        cws[i]=cws[i-1];
        cbs[i]=cbs[i-1];
        cwt[i]=cwt[i-1];
        cbt[i]=cbt[i-1];
        if(s[i-1]=='W'){
            ws.push_back(i);
            ++cws[i];
        }
        else{
            bs.push_back(i);
            ++cbs[i];
        }
        if(t[i-1]=='B'){
            bt.push_back(i);
            ++cbt[i];
        }
        else{
            wt.push_back(i);
            ++cwt[i];
        }
    }
    /*if(m==16){
            for(int i=0;i<=m;++i)
                cout<<cws[i]<<' '<<cbs[i]<<' '<<cwt[i]<<' '<<cbt[i]<<'\n';
        }*/
    ll ans=0;
    for(int i=0;i<ws.size();++i){
        int x=ws[i], y=bt[bt.size()-i-1];
        int xyz=ans;
            /*if(m==16){
                cout<<x<<' '<<y<<" : ";
            }*/
        ans+=min(cws[x-1], cbt[m]-cbt[y])+min(cbs[x-1], cwt[m]-cwt[y]);
        /*    if(m==16){
                cout<<ans-xyz<<'\n';
            }*/
    }
    for(int i=0;i<bs.size();++i){
        int x=bs[i], y=wt[wt.size()-i-1];
            int xyz=ans;
            /*if(m==16){
                cout<<x<<' '<<y<<" : ";
            }*/
            ans+=min(cws[x-1], cbt[m]-cbt[y])+min(cbs[x-1], cwt[m]-cwt[y]);
            /*if(m==16){
                cout<<ans-xyz<<"\n";
            }*/
        }
        return ans;
    }
     
    ll BW(const int &k, const string &s, const string &t){
        //cout<<"-------------------------------------\n";
        vector<int>ws, bs, wt, bt;
        memset(g, 1, sizeof(g));
        memset(h, 1, sizeof(h));
        for(int i=0;i<n;++i){
            //cout<<i<<'\n';
            if(ws.size()<k && s[i]=='W'){
                ws.push_back(i);
                g[i]=0;
            }
            if(bt.size()<k && t[i]=='B'){
                bt.push_back(i);
                h[i]=0;
            }
        }
        for(int i=n-1;i>=0;--i){
            if(bs.size()<k && s[i]=='B'){
                bs.push_back(i);
                g[i]=0;
            }
            if(wt.size()<k && t[i]=='W'){
                wt.push_back(i);
                h[i]=0;
            }
        }
        //cout<<"ok\n";
        reverse(all(bs));
        reverse(all(wt));
        //cout<<k<<'\n';
        if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
            return 0;
        //cout<<"nok\n";
        ll ans=-1LL*k*(k-1);
        for(int i=0;i<k;++i){
            ans+=bs[0]-ws[0]-1;
            ans+=wt[0]-bt[0]-1;
        }
     /*   if(k==5){
            cout<<"how : \n";
            for(int z: ws)
                cout<<z<<' ';
            cout<<'\n';
            for(int z: bs)
                cout<<z<<' ';
            cout<<'\n';
            for(int z: wt)
                cout<<z<<' ';
            cout<<'\n';
            for(int z: bt)
                cout<<z<<' ';
            cout<<'\n';
        }*/
        string ss="", tt="";
        for(int i=0;i<n;++i){
            if(g[i])
                ss+=s[i];
            if(h[i])
                tt+=t[i];
        }
        //cout<<ans<<" : "<<ss<<" "<<tt<<'\n';
        ans+=BW(ss, tt);
        //cout<<ans<<'\n';
        return ans;
    }
     
    int main(){
        //ios_base::sync_with_stdio(0); cin.tie(0);
        string s, t;
        cin>>n>>s;
        s=s[2*n-1]+s;
        s.pop_back();
        if(n>3000)
            return 0;
        t="";
        for(int i=n;i<2*n;++i)
            t+=s[i];
        reverse(all(t));
        ll ans=0;
        for(int i=0;2*i<=n;++i){
            ans=max(ans, BW(i, s, t));
            ans=max(ans, BW(i, t, s));
        }
        cout<<ans<<'\n';
    }

Compilation message

monochrome.cpp: In function 'll BW(const string&, const string&)':
monochrome.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<ws.size();++i){
      |                 ~^~~~~~~~~~
monochrome.cpp:45:13: warning: unused variable 'xyz' [-Wunused-variable]
   45 |         int xyz=ans;
      |             ^~~
monochrome.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<bs.size();++i){
      |                 ~^~~~~~~~~~
monochrome.cpp:56:17: warning: unused variable 'xyz' [-Wunused-variable]
   56 |             int xyz=ans;
      |                 ^~~
monochrome.cpp: In function 'll BW(const int&, const string&, const string&)':
monochrome.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   75 |             if(ws.size()<k && s[i]=='W'){
      |                ~~~~~~~~~^~
monochrome.cpp:79:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   79 |             if(bt.size()<k && t[i]=='B'){
      |                ~~~~~~~~~^~
monochrome.cpp:85:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   85 |             if(bs.size()<k && s[i]=='B'){
      |                ~~~~~~~~~^~
monochrome.cpp:89:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   89 |             if(wt.size()<k && t[i]=='W'){
      |                ~~~~~~~~~^~
monochrome.cpp:98:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   98 |         if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
      |            ~~~~~~~~~^~~
monochrome.cpp:98:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   98 |         if(ws.size()!=k || wt.size()!=k || (k>0 && (ws[k-1]>bs[0] || bt[k-1]>wt[0])))
      |                            ~~~~~~~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 664 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 664 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 6 ms 724 KB Output is correct
15 Incorrect 6 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 664 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 6 ms 724 KB Output is correct
15 Incorrect 6 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 664 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 6 ms 724 KB Output is correct
15 Incorrect 6 ms 724 KB Output isn't correct
16 Halted 0 ms 0 KB -