Submission #203642

#	Time	Username	Problem	Language	Result	Execution time	Memory
203642		osaaateiasavtnl	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	42 ms	7800 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7;
 
int n, k;
string s;
int num(char c) {
    if (c == 'J')
        return 0;
    else if (c == 'O')
        return 1;
    else
        return 2;
}   
 
vector <int> pos[N];
 
int getk(int i, vector <int> &a) {
    auto t = lower_bound(all(a), i);
    int p = t - a.begin();
    if (p + k - 1 >= a.size())
        return -1;
    else
        return a[p + k - 1];
}   
 
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> k >> s;
    for (int i = 0; i < n; ++i)
        pos[num(s[i])].app(i);
    int ans = N;
    for (int l = 0; l < n; ++l) {
        int t = l;
        for (int i = 0; i < 3; ++i) {
            t = getk(t, pos[i]);
            if (t == -1)
                break;
        }   
        if (t != -1)
            ans = min(ans, t - l + 1 - 3 * k);                        
    }   
    if (ans == N)
        cout << "-1\n";
    else
        cout << ans << '\n';            
}

Compilation message (stderr)

ho_t2.cpp: In function 'long long int getk(long long int, std::vector<long long int>&)':
ho_t2.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (p + k - 1 >= a.size())
         ~~~~~~~~~~^~~~~~~~~~~

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