This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std ;
const int mx = 2e5 + 5 ;
int n , k , ind[3][mx] , pos[mx] , siz[3] ;
string s ;
int bs(int low , int high , int val , int a[])
{
while(low<high)
{
int mid = (low+high)>>1 ;
if(a[mid]<val) low = mid + 1 ;
else high = mid ;
}
return low ;
}
int check(int x)
{
for(int i = 0 ; i <= x ; ++i)
{
int l = i + 1 , r = n - x + i , cnt = 0 ;
for(int j = 0 ; j < 3 ; ++j)
{
if(l>ind[j][siz[j]]) break ;
int pos = bs(1,siz[j],l,ind[j]) ;
if(((pos+k-1)<=siz[j]) && (ind[j][pos+k-1]<=r))
{
++cnt , l = ind[j][pos+k-1] + 1 ;
}
}
if(cnt==3) return 1 ;
}
return 0 ;
}
int main()
{
scanf("%d%d",&n,&k) ;
cin>>s ;
for(int i = 0 ; i < n ; ++i)
{
if(s[i]=='J')
{
++siz[0] ;
ind[0][siz[0]] = i + 1 ;
}
else if(s[i]=='O')
{
++siz[1] ;
ind[1][siz[1]] = i + 1 ;
}
else
{
++siz[2] ;
ind[2][siz[2]] = i + 1 ;
}
}
int low = 0 , high = n ;
if(!check(0))
{
puts("-1") ;
return 0 ;
}
while(low<high)
{
int mid = (low+high+1)>>1 ;
if(check(mid)) low = mid ;
else high = mid - 1 ;
}
printf("%d\n",n-low-(3*k)) ;
return 0 ;
}
Compilation message (stderr)
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%d%d",&n,&k) ;
| ~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |