Submission #203107

#	Time	Username	Problem	Language	Result	Execution time	Memory
203107		godwind	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	191 ms	48248 KiB

ho_t2

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;
 
#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228
 
 
 
template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
// random_device rnd;
 
// template<typename T> void shuffle(vector< T > &v) {
//     for (int i = 1; i < (int)v.size(); ++i) {
//         swap(v[rnd() % i], v[i]);
//     }
//     for (int i = (int)v.size() - 1; i; --i) {
//         swap(v[rnd() % i], v[i]);
//     }
// }

const int N = 200 * 1000 + 228;
const int LG = 20;

int s[N], last[3];
int p[N][3][LG];


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, K;
    cin >> n >> K;
    for (int i = 1; i <= n; ++i) {
        char c;
        cin >> c;
        if (c == 'J') {
            s[i] = 0;
        } else if (c == 'O') {
            s[i] = 1;
        } else {
            s[i] = 2;
        }
    }
    last[0] = last[1] = last[2] = n + 1;
    for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 20; ++k) {
            p[n + 1][j][k] = n + 1;
        }
    }
    for (int i = n; i; --i) {
        for (int j = 0; j < 3; ++j) {
            p[i][j][0] = last[j];
            for (int k = 1; k < LG; ++k) {
                p[i][j][k] = p[p[i][j][k - 1]][j][k - 1];
            }
        }
        last[s[i]] = i;
    }
    int answer = n + 1;
    for (int i = 1; i <= n; ++i) {
        int pos = i;
        for (int j = 0; j < 3; ++j) {
            int curK = K;
            if (s[pos] == j) curK--;
            for (int t = 0; t < LG; ++t) {
                if ((curK >> t) & 1) {
                    pos = p[pos][j][t];
                }
            }
        }
        if (pos == n + 1) continue;
        uin(answer, pos - i + 1 - 3 * K);
    }
    if (answer == n + 1) answer = -1;
    cout << answer << '\n';
    return 0;
}
// RU_023
 
 
// 
// OJIJOIOIIJ

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