제출 #1370542

#제출 시각아이디문제언어결과실행 시간메모리
1370542ValenzJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
12 ms3016 KiB
// 道草を楽しめ 大いにな。ほしいものより大切なものが きっとそっちに ころがってる
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t; // available on 64-bit targets
 
//defines
#define int long long
#define debug(x) cerr << "(" << #x << "=" << x << "," << __LINE__ << ")\n";
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);
 
//constants
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; 
const char dir[4]{'D','R','U','L'};
const int maxn=2e5+5;
const double eps=1e-9;
 
//typedefs
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
 
//Template
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <typename T, auto M> struct Mod {
    using V = conditional_t<sizeof(T) <= 4, u64, u128>;
    static V inv(V x, V m) { return x > 1 ? m - inv(m % x, x) * m / x : 1; }
    make_unsigned_t<T> x;
    Mod() : x(0) {}
    Mod(auto y) : x(y % M) { x >= M ? x += M : x; }
    operator T() const { return x; }
    Mod operator-() const { return Mod() -= *this; }
    Mod operator+(auto rhs) const { return Mod(*this) += rhs; }
    Mod operator-(auto rhs) const { return Mod(*this) -= rhs; }
    Mod operator*(auto rhs) const { return Mod(*this) *= rhs; }
    Mod operator/(auto rhs) const { return Mod(*this) /= rhs; }
    Mod &operator+=(Mod rhs) { return (x += rhs.x) >= M ? x -= M : x, *this; }
    Mod &operator-=(Mod rhs) { return (x -= rhs.x) >= M ? x += M : x, *this; }
    Mod &operator*=(Mod rhs) { return x = x * V(rhs.x) % M, *this; }
    Mod &operator/=(Mod rhs) { return x = x * inv(rhs.x, M) % M, *this; }
    Mod pow(auto y) const { // O(log y) | 0^(-inf,0] -> 1
    Mod ans(1), base(*this);
    for (auto e = y < 0 ? ~y + u128(1) : +y; e; e >>= 1, base *= base) {
        e & 1 ? ans *= base : ans;
    }
    return y < 0 ? Mod(1) /= ans : ans;
    }
};
 
using mint = Mod<int, 998244353>;

void solve()
{
    int n,m;
    cin >> n >> m;
    string s;
    cin >> s;
    map<char,vector<int>> mp;
    for(int i=0;i<n;i++)
    {
        mp[s[i]].push_back(i);
    }
    int ans=LLONG_MAX;
    for(int i=0;i<n;i++)
    {
        bool b1=0,b2=0,b3=0;
        int res=0;
        if(s[i]=='J')
        {
            int pos=lower_bound(all(mp[s[i]]),i)-mp[s[i]].begin();
            pos+=m-1;
            if(pos<sz(mp[s[i]]))
            {
                pos=mp[s[i]][pos];
                b1=1;
                pos=lower_bound(all(mp['O']),pos)-mp['O'].begin();
                if(pos<sz(mp['O']) and pos+m-1<sz(mp['O']))
                {
                    b2=1;
                    pos+=m-1;
                    pos=mp['O'][pos];
                    pos=lower_bound(all(mp['I']),pos)-mp['I'].begin();
                    if(pos<sz(mp['I']) and pos+m-1<sz(mp['I']))
                    {
                        b3=1;
                        pos+=m-1;
                        pos=mp['I'][pos];
                        res=pos-i+1-m*3;
                    }
                }
            }
        }
        if(b1 and b2 and b3)
        {
            ans=min(ans,res);
        }
    }
    if(ans==LLONG_MAX)
    {
        cout << "-1\n";
        return;
    }
    cout << ans << '\n';
}
signed main()
{
    fastio();
    int t=1;
    // cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…