Submission #1341829

#TimeUsernameProblemLanguageResultExecution timeMemory
1341829cansu_mutluJJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    string a,s;
    cin >> s;
    for(int i=0;i<k;i++) a+='J';
    for(int i=0;i<k;i++) a+='O';
    for(int i=0;i<k;i++) a+='I';
    int cnt = 0,ok = 0;
    char cur = 'I';
    int l = n-1,r = -1;
    queue<int> j,o,i;
    for(;l>=0;l--)
    {
        if(s[l]==cur)
        {
            if(cur=='J') j.push(l);
            else if(cur=='I') i.push(l);
            else o.push(l);
            cnt++;
            if(cnt==k)
            {
                if(cur=='J')
                {
                    ok = 1;
                    break;

                }
                else if(cur=='O') cur = 'J';
                else cur = 'O';
                cnt = 0;
            }
        }
        if(r==-1 && s[l]=='I')
        {
            r = l;

        }
    }
    int ans = r-l+1;
    if(ok==0)
    {
        cout << -1 << endl;
        return 0;
    }
    l--;
    for(;l>=0;l--)
    {
        if(s[cur]!='J') continue;
        j.push(cur);
        int ex = j.front();
        j.pop();
        int nw = j.front();
        for(int konum = ex;konum>nw;konum--)
        {
            if(s[konum]=='O')
            {
                o.push(konum);
            }
        }
        while(o.size()>k)
        {
          int ex = o.front();
        o.pop();
        int nw = o.front();
        for(int konum = ex;konum>nw;konum--)
        {
            if(s[konum]=='I')
            {
                i.push(konum);
            }
        }  
        }
        while(i.size()>k)
        {
            i.pop();
        }
        r = i.front();
       // cout << l << " " << r << endl;
        ans = min(ans,(i.front()-l+1));
    }
    cout << ans-(3*k) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...