Submission #783806

#	Time	Username	Problem	Language	Result	Execution time	Memory
783806		borisAngelov	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	9 ms	2060 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

vector<int> positions[3];

int decode(char c)
{
    if (c == 'J')
    {
        return 0;
    }

    if (c == 'O')
    {
        return 1;
    }

    return 2;
}

int find_first(const vector<int>& pos, int idx)
{
    int l = 0;
    int r = pos.size() - 1;

    while (l <= r)
    {
        int mid = (l + r) / 2;

        if (pos[mid] < idx)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    if (l == pos.size())
    {
        return -1;
    }

    return l;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

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

    string s;
    cin >> s;

    for (int i = 0; i < n; ++i)
    {
        positions[decode(s[i])].push_back(i);
    }

    int ans = (1 << 30);

    for (int i = 0; i < positions[0].size(); ++i)
    {
        if (i + k - 1 >= positions[0].size())
        {
            break;
        }

        //cout << "on " << positions[0][i] << endl;

        int last0 = positions[0][i + k - 1];

        int first1 = find_first(positions[1], last0);

        if (first1 == -1 || first1 + k - 1 >= positions[1].size())
        {
            break;
        }

        //cout << "first O -> " << positions[1][first1] << endl;

        int last1 = first1 + k - 1;

        //cout << "last O -> " << positions[1][last1] << endl;

        int first2 = find_first(positions[2], positions[1][last1]);

        if (first2 == -1 || first2 + k - 1 >= positions[2].size())
        {
            break;
        }

        //cout << "first I -> " << positions[2][first2] << endl;

        int last2 = first2 + k - 1;

        ans = min(ans, positions[2][last2] - positions[0][i] + 1 - 3 * k);
    }

    if (ans == (1 << 30))
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int find_first(const std::vector<int>&, int)':
ho_t2.cpp:41:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if (l == pos.size())
      |         ~~^~~~~~~~~~~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < positions[0].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if (i + k - 1 >= positions[0].size())
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:86:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if (first1 == -1 || first1 + k - 1 >= positions[1].size())
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:99:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (first2 == -1 || first2 + k - 1 >= positions[2].size())
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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