Submission #1137970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137970		VMaksimoski008	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	25 ms	12360 KiB

ho_t2

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 5;

int get(char ch) {
    if(ch == 'J') return 0;
    if(ch == 'O') return 1;
    return 2;
}

int vis[maxn][4], ans=1e9;
vector<int> G[maxn];

void dfs(int u, int t, int l) {
    if(vis[u][t]) return ;
    if(t == 3) {
        ans = min(ans, u-l+1);
        return ;
    } 

    for(int v : G[u]) dfs(v, t+1, l);
}

signed main() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
    s = "." + s;

    vector<int> pos[3];
    for(int i=1; i<=n; i++)
        pos[get(s[i])].push_back(i);

    for(int i=0; i<3; i++) {
        if(pos[i].size() < k) {
            cout << -1 << '\n';
            return 0;
        }
    }

    for(int i=0; i+k-1<pos[2].size(); i++) {
        G[pos[2][i]].push_back(pos[2][i+k-1]);
    }

    for(int t=0; t<2; t++) {
        for(int i=0; i+k-1<pos[t].size(); i++) {
            auto p = lower_bound(pos[t+1].begin(), pos[t+1].end(), pos[t][i+k-1]);
            if(p != pos[t+1].end()) {
                G[pos[t][i]].push_back(*p);
            }
        }
    }

    for(int i=1; i<=n; i++) {
        if(s[i] == 'J' && !vis[i][0]) dfs(i, 0, i);
    }
    cout << (ans == 1e9 ? -1 : ans - 3*k) << '\n';
}

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