제출 #720309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720309		thimote75	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	56 ms	3176 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>

int N, K;
string buffer;

idata J, O, I;

void cumul (idata &s) {
    for (int i = 1; i < s.size(); i ++)
        s[i] += s[i - 1];
}

int bs (idata &u, int v) {
    int a = - 1;
    int b = u.size();

    while (b - a > 1) {
        int c = (a + b) >> 1;

        if (u[c] >= v) b = c;
        else a = c;
    }

    return b;
}

int getl (idata &v, int u) {
    u --; if (u == -1) return 0;
    return v[u];
}
int find (int l) {
    int j = bs(J, getl(J, l) + K);
    if (j == N) return N;
    int o = bs(O, getl(O, j) + K);
    if (o == N) return N;
    int i = bs(I, getl(I, o) + K);

    return i;
}

int main () {
    cin >> N >> K >> buffer;

    J.resize(N);
    O.resize(N);
    I.resize(N);

    for (int i = 0; i < N; i ++) {
        if (buffer[i] == 'J') J[i] ++;
        if (buffer[i] == 'O') O[i] ++;
        if (buffer[i] == 'I') I[i] ++;
    }

    cumul(J);
    cumul(O);
    cumul(I);

    int res = N + 2;
    for (int i = 0; i < N; i ++) {
        int n = find(i);
        if (n == N) continue ;

        res = min(res, n - i);
    }

    if (res != N + 2) res -= K * 3 - 1;
    else res = -1;

    cout << res << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t2.cpp: In function 'void cumul(std::vector<int>&)':
ho_t2.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 1; i < s.size(); i ++)
      |                     ~~^~~~~~~~~~

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