Submission #936337

#	Time	Username	Problem	Language	Result	Execution time	Memory
936337		DobromirAngelov	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	9 ms	2256 KiB

ho_t2

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int n,k;
string s;
vector<int> pos[3];

int bs(int x,int c)
{
    if(pos[c].back()<=x) return -1;
    int l=0,r=pos[c].size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(pos[c][mid]>x) r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>k;
cin>>s;

for(int i=0;i<n;i++)
{
    if(s[i]=='J') pos[0].push_back(i);
    if(s[i]=='O') pos[1].push_back(i);
    if(s[i]=='I') pos[2].push_back(i);
}

if(pos[0].size()<k || pos[1].size()<k || pos[2].size()<k)
{
    cout<<-1<<endl;
    return 0;
}

int ans=n+1;
for(int i=k-1;i<pos[0].size();i++)
{
    int cur=pos[0][i]-pos[0][i-k+1]+1-k;
    int ind=bs(pos[0][i],1);
    if(ind==-1 || ind>pos[1].size()-k) break;
    cur+=pos[1][ind]-pos[0][i]-1;
    cur+=pos[1][ind+k-1]-pos[1][ind]+1-k;
    int ind2=bs(pos[1][ind+k-1],2);
    if(ind2==-1 || ind2>pos[2].size()-k) break;
    cur+=pos[2][ind2]-pos[1][ind+k-1]-1;
    cur+=pos[2][ind2+k-1]-pos[2][ind2]+1-k;
    ans=min(ans, cur);
}

if(ans>n) cout<<-1<<endl;
else cout<<ans<<endl;

return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:39:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 | if(pos[0].size()<k || pos[1].size()<k || pos[2].size()<k)
      |    ~~~~~~~~~~~~~^~
ho_t2.cpp:39:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 | if(pos[0].size()<k || pos[1].size()<k || pos[2].size()<k)
      |                       ~~~~~~~~~~~~~^~
ho_t2.cpp:39:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 | if(pos[0].size()<k || pos[1].size()<k || pos[2].size()<k)
      |                                          ~~~~~~~~~~~~~^~
ho_t2.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 | for(int i=k-1;i<pos[0].size();i++)
      |               ~^~~~~~~~~~~~~~
ho_t2.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if(ind==-1 || ind>pos[1].size()-k) break;
      |                   ~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if(ind2==-1 || ind2>pos[2].size()-k) break;
      |                    ~~~~^~~~~~~~~~~~~~~~

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