Submission #735580

#	Time	Username	Problem	Language	Result	Execution time	Memory
735580		sandry24	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	11 ms	2016 KiB

ho_t2

#include <bits/stdc++.h>
//#include "horses.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

int get_ind(char c){
    switch(c){
    case 'J': return 0;
    case 'O': return 1;
    case 'I': return 2;
    };
}

void solve(){
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    //[0] - J
    //[1] - O
    //[2] - I
    vector<vi> ind(3);
    for(int i = 0; i < n; i++)
        ind[get_ind(s[i])].pb(i);
    int l = -1, r = 1e9;
    for(int i = 0; i < ind[0].size(); i++){
        if(i + k - 1 >= ind[0].size())
            continue;
        int cur = ind[0][i+k-1];
        int h = lower_bound(ind[1].begin(), ind[1].end(), cur) - ind[1].begin();
        if(h + k - 1 >= ind[1].size())
            continue;
        cur = ind[1][h+k-1];
        h = lower_bound(ind[2].begin(), ind[2].end(), cur) - ind[2].begin();
        if(h + k - 1 >= ind[2].size())
            continue;
        cur = ind[2][h+k-1];
        if((cur - ind[0][i]) < (r - l)){
            l = ind[0][i];
            r = cur;
        }
    }
    if(l == -1)
        cout << -1 << '\n';
    else {
        //cout << l << ' ' << r << ' ' << string(s.begin()+l, s.begin()+r+1) << '\n';
        cout << r - l + 1 - 3*k << '\n';
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0; i < ind[0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
ho_t2.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(i + k - 1 >= ind[0].size())
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if(h + k - 1 >= ind[1].size())
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(h + k - 1 >= ind[2].size())
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp: In function 'int get_ind(char)':
ho_t2.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

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