Submission #202627

#	Time	Username	Problem	Language	Result	Execution time	Memory
202627		SamAnd	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	43 ms	2940 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n, k;
char a[N];

int p[N][3];

int byn(int x, int j)
{
    int l = x, r = n;
    int ans = n + 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (p[m][j] - p[x - 1][j] >= k)
        {
            ans = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &k);
    scanf(" %s", (a + 1));
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] == 'J')
            a[i] = 0;
        else if (a[i] == 'O')
            a[i] = 1;
        else
            a[i] = 2;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 3; ++j)
            p[i][j] = p[i - 1][j];
        p[i][a[i]]++;
    }
    int ans = N;
    for (int i = 1; i <= n; ++i)
    {
        int x = byn(i, 0);
        x = byn(x + 1, 1);
        x = byn(x + 1, 2);
        if (x <= n)
            ans = min(ans, x - i + 1 - 3 * k);
    }
    if (ans == N)
        printf("-1\n");
    else
        printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:45:18: warning: array subscript has type 'char' [-Wchar-subscripts]
         p[i][a[i]]++;
                  ^
ho_t2.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t2.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", (a + 1));
     ~~~~~^~~~~~~~~~~~~~~~

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