Submission #393599

#	Time	Username	Problem	Language	Result	Execution time	Memory
393599		79brue	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	198 ms	47648 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
char s[200005];
int ans = INT_MAX;

int sparse[200005][20][3];

void makeSparse(){
    int recent[3] = {n+1, n+1, n+1};
    sparse[n+1][0][0] = sparse[n+1][0][1] = sparse[n+1][0][2] = n+1;
    for(int i=n; i>=0; i--){
        for(int j=0; j<3; j++) sparse[i][0][j] = recent[j];
        if(s[i] == 'J') recent[0] = i;
        else if(s[i] == 'O') recent[1] = i;
        else recent[2] = i;
    }

    for(int d=1; d<20; d++){
        for(int i=0; i<=n+1; i++){
            for(int j=0; j<3; j++){
                sparse[i][d][j] = sparse[sparse[i][d-1][j]][d-1][j];
            }
        }
    }
}

int kth(int x, int len, int y){
    for(int d=0; d<20; d++){
        if((len>>d) & 1) x = sparse[x][d][y];
    }
    return x;
}

int main(){
    scanf("%d %d %s", &n, &k, s+1);
    makeSparse();

    for(int i=1; i<=n; i++){
        int tmp = i-1;
        tmp = kth(tmp, k, 0);
        tmp = kth(tmp, k, 1);
        tmp = kth(tmp, k, 2);
        if(tmp != n+1) ans = min(ans, (n-3*k) - (n-tmp) - (i-1));
    }
    printf("%d\n", ans == INT_MAX ? -1 : ans);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d %d %s", &n, &k, s+1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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