Submission #625268

#	Time	Username	Problem	Language	Result	Execution time	Memory
625268		boris_mihov	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	0 ms	212 KiB

ho_t2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <deque>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;

int n, k;
char s[MAXN];
std::deque <int> byLetter[3];

int search(int idx, int pos)
{
    int l = 0, r = byLetter[idx].size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (byLetter[idx][mid] < pos) l = mid;
        else r = mid;
    }

    if (l + k <= (int)byLetter[idx].size()-1) return byLetter[idx][l + k];
    return -1;
}

bool check(int deleted)
{
    if (n - deleted < 3*k) return false;
    byLetter[0].clear();
    byLetter[1].clear();
    byLetter[2].clear();
    for (int i = n ; i >= 1 ; --i)
    {
        if (s[i] == 'J') byLetter[0].push_front(i);
        if (s[i] == 'O') byLetter[1].push_front(i);
        if (s[i] == 'I') byLetter[2].push_front(i);
        if (i <= deleted)
        {
            int endLetter = n - deleted + i;
            if (s[endLetter] == 'J') byLetter[0].pop_back();
            if (s[endLetter] == 'O') byLetter[1].pop_back();
            if (s[endLetter] == 'I') byLetter[2].pop_back();
        }

        if (byLetter[0].size() >= k)
        {
            int pos = search(1, byLetter[0][k-1]);
            if (pos != -1) pos = search(2, pos);
            if (pos != -1) return true;
        }
    }

    return false;
}

void solve()
{
    int l = 0, r = n + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }    

    if (l == 0) std::cout << -1 << '\n';
    else std::cout << n - 3*k - l << '\n';
}

void read()
{
    std::cin >> n >> k;
    std::cin >> s + 1;
}

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

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'bool check(int)':
ho_t2.cpp:48:32: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if (byLetter[0].size() >= k)
      |             ~~~~~~~~~~~~~~~~~~~^~~~
ho_t2.cpp: In function 'void read()':
ho_t2.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     std::cin >> s + 1;
      |                 ~~^~~

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