Submission #1114726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114726		tkwiatkowski	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	336 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

vector<int> sumki_J(string napis,int k,int n){
    vector<int>wynik(1),sumy(1);
    int suma=0,index=-1;
    bool czybyl=false;
    queue<int>NIENAWIDZETEGOGOWNA;
    for(int i=0;i<n;++i){
        if(napis[i]=='J') {
            if(index==-1) {
                index=i;
                NIENAWIDZETEGOGOWNA.push(i);
            }
            suma++;
            
        }
        else{ 
            if(suma>0)
                sumy.push_back(sumy[i]+1);
            else
                sumy.push_back(sumy[i]);
        }
        if(suma==k && napis[i]=='J'){
            czybyl=true;
            sumy.push_back(sumy[i]-sumy[NIENAWIDZETEGOGOWNA.front()]);
            index=i;
            NIENAWIDZETEGOGOWNA.push(i);
            NIENAWIDZETEGOGOWNA.pop();
            suma--;
        }
        else if(napis[i]=='J')
            sumy.push_back(sumy[i]);
        if(czybyl==true)
            wynik.push_back(sumy[i+1]);
        else
            wynik.push_back(-1);
    }
    return wynik;
}
vector<int> sumki_I(string napis,int k,int n){
    vector<int>wynik(1),sumy(1);
    int suma=0,index=-1;
    bool czybyl=false;
    queue<int>jebac;
    for(int i=n-1;i>=0;--i){
        if(napis[i]=='I') {
            if(index==-1) {
                index=n-i-1;
                jebac.push(index);
            }
            suma++;
        }
        else{ 
            if(suma>0)
                sumy.push_back(sumy[n-i-1]+1);
            else
                sumy.push_back(sumy[n-i-1]);
        }
        if(suma==k && napis[i]=='I'){
            czybyl=true;
            sumy.push_back(sumy[n-i-1]-sumy[jebac.front()]);
            index=n-i-1;
            jebac.push(index);
            jebac.pop();
            suma--;
        }
        else if(napis[i]=='I')
            sumy.push_back(sumy[n-i-1]);
        if(czybyl==true)
            wynik.push_back(sumy[n-i]);
        else
            wynik.push_back(-1);
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,k,s=0;
    string napis;
    cin >> n >> k;
    cin >> napis;
    vector<int>sum_I=sumki_I(napis,k,n);
    vector<int>sum_J=sumki_J(napis,k,n);
    vector<int>sum_O(1);
    queue<int>pozycje;
    for(int i=0;i<n;++i){
        if(napis[i]=='O')
            sum_O.push_back(sum_O[i]);
        else
            sum_O.push_back(sum_O[i]+1);
    }
    
    
    int wynik=1000000;
    int s1,s2,gowno;
    reverse(sum_I.begin(),sum_I.end());
    /*for(int i=0;i<n;++i){
        cout << sum_J[i] << ' ';    
    }
    cout << endl;

    
    for(int i=0;i<n;++i){
        cout << sum_I[i] << ' ';    
    }
    cout << endl;
    */
    for(int i=0;i<n;++i){   

        if(napis[i]=='O'){
            s++;
            pozycje.push(i);
        }   
        if(s==k){
            s--;
            s2=sum_J[pozycje.front()];
            
            gowno=sum_O[i+1]-sum_O[pozycje.front()];
            //cout << gowno << ' ' ;
            s1=sum_I[pozycje.front()+gowno+k ];
            //cout << s1 << ' ' << s2 << endl;

            //cout << s1 << ' ' << s2 << endl;
            if(s1!=-1 && s2!=-1)
                wynik=min(wynik,s1+s2+gowno);
            pozycje.pop();

        }
    }
    if(wynik!=1000000)
        cout << wynik;
    else
        cout << -1;
    return 0;
}

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