Submission #857015

#	Time	Username	Problem	Language	Result	Execution time	Memory
857015		StefanSebez	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	16 ms	13584 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int inf=1e18;
signed main()
{
    int n,k;cin>>n>>k;
    string s;cin>>s;
    int a[n+1],pref[4][n+1];
    memset(pref,0,sizeof(pref));
    vector<int>b[4];
    for(int i=1;i<=n;i++)
	{
		if(s[i-1]=='J') a[i]=1;
		if(s[i-1]=='O') a[i]=2;
		if(s[i-1]=='I') a[i]=3;
		for(int j=1;j<=3;j++)
		{
			pref[j][i]=pref[j][i-1];
			if(j==a[i]) pref[j][i]++;
		}
		b[a[i]].pb(i);
	}
	bool bul=true;
	for(int j=1;j<=3;j++)
	{
		if(pref[j][n]<k) bul=false;
	}
	if(!bul)
	{
		cout<<"-1\n";
		return 0;
	}
	int I[n+1]={0};
	for(int i=1,j=0;i<=n;i++)
	{
		if(a[i]!=1 && pref[1][i]>0) I[i]=I[i-1]+1;
		else
		{
			I[i]=I[i-1];
			if(pref[1][i]>k)
			{
				I[i]-=b[1][j+1]-b[1][j]-1;
				j++;
			}
		}
	}
	int J[n+50]={0};
	for(int i=n,j=b[3].size()-1;i>=1;i--)
	{
		if(a[i]!=3 && pref[3][n]-pref[3][i-1]>0) J[i]=J[i+1]+1;
		else
		{
			J[i]=J[i+1];
			if(pref[3][n]-pref[3][i-1]>k)
			{
				J[i]-=b[3][j]-b[3][j-1]-1;
				j--;
			}
		}
	}
	/*for(int i=1;i<=n;i++) cout<<I[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++) cout<<J[i]<<" ";
	cout<<endl;*/
	int res=inf,sum=0;
	for(int i=1;i<=k-1;i++)
	{
		sum+=b[2][i]-b[2][i-1]-1;
	}
	for(int j=k-1;j<b[2].size();j++)
	{
		int x=sum;
		x+=I[b[2][j-(k-1)]-1];
		x+=J[b[2][j]+1];
		if(pref[1][b[2][j-(k-1)]-1]<k || pref[3][n]-pref[3][b[2][j]]<k) x=inf;
		res=min(res,x);
		if(j+1<b[2].size())sum+=b[2][j+1]-b[2][j]-1;
		sum-=b[2][j-(k-1)+1]-b[2][j-(k-1)]-1;
	}
	if(res>=inf) res=-1;
	cout<<res<<endl;
	/*for(int i=1;i<=n;i++)
	{
		bool bul=true;
		for(int j=1;j<=3;j++) if(pref[j][i]<k) bul=false;
		if(!bul) continue;
		int ind=inf;
		for(int j=1;j<=3;j++)
		{
			int lb=lower_bound(pref[j],pref[j]+n+1,pref[j][i]-k)-pref[j];
			ind=min(ind,lb);
		}
        int x=0;
        for(int j=1;j<=3;j++)
		{
			x+=pref[j][i]-pref[j][ind]-k;
		}
		res=min(res,x);
		cout<<i<<" "<<ind<<endl;
	}*/
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:72:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int j=k-1;j<b[2].size();j++)
      |                ~^~~~~~~~~~~~
ho_t2.cpp:79:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if(j+1<b[2].size())sum+=b[2][j+1]-b[2][j]-1;
      |      ~~~^~~~~~~~~~~~

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