Submission #530864

#	Time	Username	Problem	Language	Result	Execution time	Memory
530864		ToroTN	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	9 ms	3264 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
int n,m,l[200005],r[200005],ans=1e9,ll,rr;
char s[200005];
vector<int> v[3];
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='J')
        {
            v[0].push_back(i);
        }else if(s[i]=='O')
        {
            v[1].push_back(i);
        }else
        {
            v[2].push_back(i);
        }
    }
    /*for(int i=0;i<3;i++)
    {
        printf("%d\n",i);
        for(int j=0;j<v[i].size();j++)
        {
            printf("%d ",v[i][j]);
        }
        printf("\n");
    }*/
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
    {
        printf("-1\n");
    }else
    {
        for(int i=m-1;i<v[0].size();i++)
        {
            if(i==v[0].size()-1)
            {
                for(int j=v[0][i];j<=n;j++)
                {
                    l[j]=v[0][i-m+1];
                }
            }else
            {
                for(int j=v[0][i];j<v[0][i+1];j++)
                {
                    l[j]=v[0][i-m+1];
                }
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("%d ",l[i]);
        }
        printf("\n");*/
        for(int i=v[2].size()-m;i>=0;i--)
        {
            //printf("%d\n",i);
            if(i==0)
            {
                for(int j=v[2][i];j>=1;j--)
                {
                    r[j]=v[2][i+m-1];
                }
            }else
            {
                for(int j=v[2][i];j>v[2][i-1];j--)
                {
                    r[j]=v[2][i+m-1];
                }
            }
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("%d ",r[i]);
        }
        printf("\n");*/
        for(int i=m-1;i<v[1].size();i++)
        {
            ll=v[1][i-m+1];
            rr=v[1][i];
            //printf("%d %d %d %d\n",ll,rr,l[ll],r[rr]);
            if(l[ll]!=-1&&r[rr]!=-1)
            {
                ans=min(ans,r[rr]-l[ll]+1-3*m);
            }
        }
        if(ans==1e9)
        {
            printf("-1\n");
        }else
        {
            printf("%d\n",ans);
        }
    }
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:34:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |        ~~~~~~~~~~~^~
ho_t2.cpp:34:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |                       ~~~~~~~~~~~^~
ho_t2.cpp:34:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(v[1].size()<m||v[0].size()<m||v[2].size()<m)
      |                                      ~~~~~~~~~~~^~
ho_t2.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=m-1;i<v[0].size();i++)
      |                       ~^~~~~~~~~~~~
ho_t2.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(i==v[0].size()-1)
      |                ~^~~~~~~~~~~~~~~
ho_t2.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=m-1;i<v[1].size();i++)
      |                       ~^~~~~~~~~~~~
ho_t2.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
ho_t2.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%s",s+1);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87