Submission #1114700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114700		tkwiatkowski	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	21 ms	11092 KiB

ho_t2

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

vector<pair<i64, i64>> J;
vector<pair<i64, i64>> O;
vector<pair<i64, i64>> I;
string s;
i64 N, K;

void fun(char c, vector<i64>& poz)
{
    for (i64 i = 0; i < N; i++)
    {
        if (s[i] == c)
        {
            poz.push_back(i);
        }
    }
}

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

    cin >> N >> K >> s;

    i64 j = 0, o = 0, i = 0;
    for (i64 l = 0; l < N; l++)
    {
        if (s[l] == 'J') j++;
        else if (s[l] == 'O') o++;
        else i++;
    }
    if (j < K || o < K || i < K)
    {
        cout << "-1\n";
        return 0;
    }

    vector<i64> Jot;
    fun('J', Jot);
    for (i64 l = K - 1; l < Jot.size(); l++)
    {
        J.push_back({Jot[l - K + 1], Jot[l]});
    }
    vector<i64> Oot;
    fun('O', Oot);
    for (i64 l = K - 1; l < Oot.size(); l++)
    {
        O.push_back({Oot[l - K + 1], Oot[l]});
    }
    vector<i64> Iot;
    fun('I', Iot);
    for (i64 l = K - 1; l < Iot.size(); l++)
    {
        I.push_back({Iot[l - K + 1], Iot[l]});
    }

    i64 minn = INT64_MAX;
    for (i64 l = 0; l < O.size(); l++)
    {
        if (J[0].second > O[l].first || I[I.size() - 1].first < O[l].second)
        {
            continue;
        }

        //cout << l << " :: " << O[l].first << " : " << O[l].second << "\n";

        i64 poczciag, konciag;
        i64 pocz = 0, kon = J.size() - 1, srodek;
        while (pocz < kon)
        {
            srodek = (pocz + kon + 1) / 2;
            if (J[srodek].second < O[l].first)
            {
                pocz = srodek;
            }
            else
            {
                kon = srodek - 1;
            }
        }
        poczciag = J[pocz].first;
        //cout << J[pocz].first << " : " << J[pocz].second << "\n";

        pocz = 0, kon = I.size() - 1;
        while (pocz < kon)
        {
            srodek = (pocz + kon) / 2;
            if (I[srodek].first > O[l].second)
            {
                kon = srodek;
            }
            else
            {
                pocz = srodek + 1;
            }
        }
        konciag = I[pocz].second;
        //cout << I[pocz].first << " : " << I[pocz].second << "\n";

        minn = min(minn, konciag - poczciag + 1 - K * 3);
    }

    if (minn == INT64_MAX)
    {
        cout << "-1\n";
        return 0;
    }
    cout << minn << "\n";

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:44:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (i64 l = K - 1; l < Jot.size(); l++)
      |                         ~~^~~~~~~~~~~~
ho_t2.cpp:50:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (i64 l = K - 1; l < Oot.size(); l++)
      |                         ~~^~~~~~~~~~~~
ho_t2.cpp:56:27: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (i64 l = K - 1; l < Iot.size(); l++)
      |                         ~~^~~~~~~~~~~~
ho_t2.cpp:62:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (i64 l = 0; l < O.size(); l++)
      |                     ~~^~~~~~~~~~

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