Submission #839702

#	Time	Username	Problem	Language	Result	Execution time	Memory
839702		sleepntsheep	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	10068 KiB

ho_t2

#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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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