Submission #702666

#	Time	Username	Problem	Language	Result	Execution time	Memory
702666		speedyArda	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	16 ms	2272 KiB

ho_t2

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5+5;
int pref_o[MAXN];
// Sol O(nlogn) (Binary search) -> Let's iterate through 'j' chars and apply binary search from their indexes. Let's start by finding kth j and go from there. That means the j we are chosing is the last j and it would be best to get the closest j which makes k times j characters. After that let's apply binary search for first 'i' index. We can apply binary search to 'i' indexes where we know that we can have k times 'i' characters starting from this index. Again it would be best find the closest 'i' character which makes k times 'i' character. After that in the binary search iteration, we need to look whether our 'i' character index is smaller than 'j' index and whether we have k times 'o' character when our last 'j' index and first 'i' index. If we have we can compare our current value with our answer (minimize it) and try to decrease our search space by decreasing first 'i' potential indexes (r = m - 1). Else we try to increase the first 'i' potential indexes (l = m + 1). Since we can have at max n 'j' characters and n 'i' characters our complexity would be O(nlogn).
int main() 
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> j_idx, i_idx;
    for(int i = 0; i < n; i++)
    {
        pref_o[i] = 0;
        if(i > 0)
            pref_o[i] = pref_o[i - 1];
        if(s[i] == 'J')
            j_idx.push_back(i);
        else if(s[i] == 'O')
            pref_o[i]++;
        else
            i_idx.push_back(i);
        
    }

    int ans = 1e9;
    for(int i = k - 1; i < j_idx.size(); i++)
    {
        int j_dif = j_idx[i] - j_idx[i - (k - 1)] - (k-2) - 1;

        int l = 0, r = i_idx.size() - 1 - k + 1;
        while(l <= r)
        {
            int m = (l + r) / 2; // First i;
            if(i_idx[m] < j_idx[i])
            {
                l = m + 1;
                continue;
            }
            int temp = j_dif + (i_idx[m + k - 1] - i_idx[m] - (k-2) - 1);
            int first_i = i_idx[m];
            int last_j = j_idx[i];
            if(pref_o[first_i] - pref_o[last_j] >= k)
            {
                temp += first_i - last_j - k - 1;
                ans = min(ans, temp);
                r = m - 1;
            } else
                l = m + 1;
            //cout << ans << "  " << j_idx[i] << " " << i_idx[m] << " " << i << " " << m << "\n";
        }

        
    }

    if(ans == 1e9)
        cout << "-1\n";
    else
        cout << ans << "\n";
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = k - 1; i < j_idx.size(); i++)
      |                        ~~^~~~~~~~~~~~~~

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