Submission #1114698

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

ho_t2

#include<bits/stdc++.h>

using namespace std; 

#define ll long long
#define fir first
#define sec second

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 

    int n, k; cin >> n >> k;

    string s; cin >> s;
    //s = ' ' + s + ' ';
    int big = pow(10, 9); 

    vector<pair<int, int>> prefJ(n+2); // od 1
    vector<pair<int, int>> sufI(n+2); // od 1

    vector<int> J; 
    for (int i = 0; i < n; i++){
        if(s[i] == 'J'){
            J.push_back(i); 
        }

        if(J.size() >= k){
            prefJ[i].first = J[J.size() - k];
            prefJ[i].second = J[J.size() - 1];  
        } else{
            prefJ[i] = {-1, -1}; 
        }
    }
    
    vector<int> I; 
    for (int i = n-1; i >= 0; i--){
        if(s[i] == 'I'){
            I.push_back(i); 
        }

        if(I.size() >= k){
            sufI[i].first = I[I.size() - k]; 
            sufI[i].second = I[I.size()-1]; 
        } else{
            sufI[i] = {-1, -1}; 
        }
    }
    
    // Mam najblizszy indeksy k*J i k*I
    deque<int> O;
    bool dasie = 0; 
    int res = 0; 
    for (int i = 0; i < n; i++){
        if(prefJ[i].first == -1 || sufI[i].second == -1){
            continue; 
        }
        
        if(s[i] == 'O'){
            O.push_back(i);
            if(O.size() > k){
                O.pop_front(); 
            }
        }

        if(O.size() >= k){ 
            dasie = 1; 

            int pozny_i_O = O[O.size()-1]; 
            int wczesny_i_O = O[O.size()-k];  
            int joty = prefJ[wczesny_i_O].first; 
            int ioty = sufI[pozny_i_O].first;
            // cout << wczesny_i_O << ' ' << pozny_i_O << '\n'; 
            // cout <<  << '\n'; 
            int h = ioty - joty - 3*k + 1;
            res = max(res, h);
        }
    }

    if(dasie){
        cout << res << '\n';
    } else{
        cout << -1 << '\n';
    }


    // for (int i = 0; i < n; i++){
    //     cout << "J " << prefJ[i].first << ' ' << prefJ[i].second << '\n';
    // }
    // for (int i = 0; i < n; i++){
    //     cout << "I " << sufI[i].first << ' ' << prefJ[i].second << '\n';
    // }
    

     
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:27:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |         if(J.size() >= k){
      |            ~~~~~~~~~^~~~
ho_t2.cpp:41:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         if(I.size() >= k){
      |            ~~~~~~~~~^~~~
ho_t2.cpp:60:25: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |             if(O.size() > k){
      |                ~~~~~~~~~^~~
ho_t2.cpp:65:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if(O.size() >= k){
      |            ~~~~~~~~~^~~~
ho_t2.cpp:16:9: warning: unused variable 'big' [-Wunused-variable]
   16 |     int big = pow(10, 9);
      |         ^~~

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