This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
int n, k, f[N][4], far_pos[N][4], near_pos[N][4];
char s[N];
int cnt(int l, int r, int c) { return f[r][c] - f[l-1][c]; }
int suf(int l, int c) { return f[n][c] - f[l-1][c]; }
#define chmax(a, b) a = std::max(a, b)
#define chmin(a, b) a = std::min(a, b)
int ok(int m)
{
/* get O's from l to r */
/*
* --JJJJOOOOOOOOOOOOOIIII-
* l r
*/
int cost[4] = {0};
for (int r = 1; r <= n; ++r)
{
/* c[r][1] - c[l-1][1] == k
* c[l-1][1] == c[r][1] - m */
if (f[r][2] < k) continue;
int l = far_pos[f[r][2] - k][2] + 1;
cost[2] = r-l+1-k;
/* f[l-1][1] - c[l0-1][1] == m
* c[l0-1][1] == f[l-1][1] - m */
if (f[l-1][1] < k) continue;
int l0 = far_pos[f[l-1][1] - k][1] + 1;
//if (l0 > 1e9) continue;
cost[1] = l-1-l0+1-k;
/* f[r1][3] - f[r][3] == k
* f[r1][3] == k + f[r][3] */
int r1 = near_pos[k + f[r][3]][3];
if (r1 == -1) continue;
cost[3] = r1-r-k;
if (cost[1] + cost[2] + cost[3] <= m)
{
//printf("(%d@%d): %d %d - %d %d - %d %d\n",m,r,l0,l-1,l,r,r+1,r1);
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d%s", &n, &k, s + 1);
for (int i = 1; i <= n; ++i) for (int j = 0; j < 3; ++j) if (j["JOI"] == s[i]) s[i] = j + 1;
for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 3; ++j) f[i][j] = f[i-1][j]; ++f[i][s[i]]; }
memset(far_pos, -1, sizeof far_pos);
memset(near_pos, 63, sizeof near_pos);
for (int i = 0; i <= n; ++i) for (int j = 1; j <= 3; ++j) far_pos[f[i][j]][j] = i;
for (int i = n; i >= 1; --i)
for (int j = 1; j <= 3; ++j) near_pos[f[i][j]][j] = i;
//for (int i = 1; i <= n; ++i) for (int j = 1; j <= 3; ++j) chmax(far_pos[f[i][j]][j], far_pos[f[i][j]-1][j]);
int l = 0, r = n - 1, z = -1;
while (l <= r)
{
int m = (l+r)/2;
if (ok(m)) r=m-1, z=m;
else l=m+1;
}
printf("%d", z);
return 0;
}
Compilation message (stderr)
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:56:96: warning: array subscript has type 'char' [-Wchar-subscripts]
56 | for (int i = 1; i <= n; ++i) { for (int j = 1; j <= 3; ++j) f[i][j] = f[i-1][j]; ++f[i][s[i]]; }
| ~~~^
ho_t2.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d%s", &n, &k, s + 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |