Submission #391000

#	Time	Username	Problem	Language	Result	Execution time	Memory
391000		wildturtle	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	15 ms	6368 KiB

ho_t2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,minn,j;
ll A[500005],Ain[500005],L[500005],R[500005];
queue <ll> q;
string s;
int main() {
    cin>>n>>k>>s;
    for(ll i=0;i<s.size();i++) {
        if(s[i]=='O') {
            a++;
            A[a]=i;
            Ain[i]=a;
        }
    }
    for(ll i=0;i<s.size();i++) {
        if(s[i]=='J') {
            q.push(i);
            if(q.size()>k) q.pop();
        }
        if(s[i]=='O') {
            if(q.size()==k) L[i]=q.front();
            else L[i]=-1;
        }
    }
    while(!q.empty()) q.pop();
    for(ll i=s.size()-1;i>=0;i--) {
        if(s[i]=='I') {
            q.push(i);
            if(q.size()>k) q.pop();
        }
        if(s[i]=='O') {
            if(q.size()==k) R[i]=q.front();
            else R[i]=-1;
        }
    }
    minn=1e18;
    for(ll i=0;i<s.size();i++) {
        if(s[i]=='O') {
            j=A[Ain[i]+k-1];
            if(Ain[i]+k-1>a) continue;
            //cout<<i<<" "<<j<<" "<<L[i]<<" "<<R[j]<<endl;
            if(L[i]==-1 || R[j]==-1) continue;
            minn=min(minn,R[j]-L[i]+1-k*3);
        }
    }
    if(minn==1e18) cout<<-1;
    else cout<<minn;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:10:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(ll i=0;i<s.size();i++) {
      |                ~^~~~~~~~~
ho_t2.cpp:17:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(ll i=0;i<s.size();i++) {
      |                ~^~~~~~~~~
ho_t2.cpp:20:24: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |             if(q.size()>k) q.pop();
      |                ~~~~~~~~^~
ho_t2.cpp:23:24: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |             if(q.size()==k) L[i]=q.front();
      |                ~~~~~~~~^~~
ho_t2.cpp:31:24: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |             if(q.size()>k) q.pop();
      |                ~~~~~~~~^~
ho_t2.cpp:34:24: warning: comparison of integer expressions of different signedness: 'std::queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |             if(q.size()==k) R[i]=q.front();
      |                ~~~~~~~~^~~
ho_t2.cpp:39:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(ll i=0;i<s.size();i++) {
      |                ~^~~~~~~~~

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