oj.uz

Submission #361351

# Submission time Handle Problem Language Result Execution time Memory
361351 2021-01-29T11:56:45 Z shahriarkhan JJOOII 2 (JOI20_ho_t2) C++14
0 / 100
 2000 ms 364 KB 
#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 ;
        if(check(mid)) low = mid ;
        else high = mid - 1 ;
    }
    printf("%d\n",n-low-(3*k)) ;
    return 0 ;
}

Compilation message

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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 2077 ms 364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 2077 ms 364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 2077 ms 364 KB Time limit exceeded
3 Halted 0 ms 0 KB -