Submission #623145

#	Time	Username	Problem	Language	Result	Execution time	Memory
623145		Mahdi	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	116 ms	1136 KiB

monochrome

#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[i]-ws[i]-1;
            ans+=wt[i]-bt[i]-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 (stderr)

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 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65