Submission #361352

#	Time	Username	Problem	Language	Result	Execution time	Memory
361352		shahriarkhan	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	339 ms	1692 KiB

ho_t2

#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) ;
      |     ~~~~~^~~~~~~~~~~~~~

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