Submission #623118

#	Time	Username	Problem	Language	Result	Execution time	Memory
623118		Mahdi	Monochrome Points (JOI20_monochrome)	C++17	0 / 100	1 ms	596 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])+min(cws[m]-cws[x], cbt[y-1])+min(cbs[m]-cbs[x], cwt[y-1]);
    /*    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])+min(cws[m]-cws[x], cbt[y-1])+min(cbs[m]-cbs[x], cwt[y-1]);
        /*if(m==16){
            cout<<ans-xyz<<"\n";
        }*/
    }
    return ans/2;
}

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;
    if(n>3000)
        return 0;
    t="";
    for(int i=n;i<2*n;++i)
        t+=s[i];
    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:13: 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:21: 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:21: 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:21: 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:21: 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:17: 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:33: 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: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65