Submission #1341832

#TimeUsernameProblemLanguageResultExecution timeMemory
1341832cansu_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;
    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;
            }
        }
        
    }
    int ans = i.front()-l+1;
    if(ok==0)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << l << " "<< r << endl;
    l--;
    for(;l>=0;l--)
    {
        if(s[l]!='J') continue;
        j.push(l);
        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));
    }
    assert(ans>=(3*k));
    cout << ans-(3*k) << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...