Submission #202879

#TimeUsernameProblemLanguageResultExecution timeMemory
202879EntityITJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
110 ms3204 KiB
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

map<char, int> label{ { 'J', 0 }, { 'O', 1 }, { 'I', 2 } };

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, k; string s; cin >> n >> k >> s;

  vector<array<int, 3> > pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i];
    ++pref[i + 1][ label[ s[i] ] ];
  }
  auto get = [&](int be, int en, char c) { return pref[en][ label[c] ] - pref[be][ label[c] ]; };

  auto findPos = [&](int i, char c) {
    int l = i, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (get(i, mid + 1, c) >= k) r = mid;
      else l = mid + 1;
    }
    return l;
  };

  int ans = inf;
  for (int i = 0; i < n; ++i) {
    int j = findPos(findPos(findPos(i, 'J'), 'O'), 'I');
    if (j < n) asMn(ans, j - i + 1 - 3 * k);
  }

  cout << (ans == inf ? -1 : ans) << '\n';

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...