Submission #754946

#	Time	Username	Problem	Language	Result	Execution time	Memory
754946		abysmal	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	6 ms	2104 KiB

ho_t2

#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>

using namespace std;

const int64_t INF = 1e18 + 5;
const int64_t mINF = 1e9 + 5;
const int64_t MOD = 1e9 + 7;
const int nbit = 31;
const int nchar = 26;
const int D = 4;
int dr[D] = {1, -1, -1, 1};
int dc[D] = {1, 1, 1, -1};

struct Solution
{
    int n;
    int k;
    string s;
    Solution() {}

    void solve()
    {
        cin >> n >> k >> s;

        vector<int> posj;
        vector<int> poso;
        vector<int> posi;
        for(int i = 0; i < n; i++)
        {
            if(s[i] == 'J') posj.push_back(i);
            if(s[i] == 'O') poso.push_back(i);
            if(s[i] == 'I') posi.push_back(i);
        }

        int j = k - 1;
        int lo = 0;
        int ro = 0;
        int li = 0;
        int ri = 0;
        int ans = mINF;
        while(j < (int) posj.size() && ro < (int) poso.size() && ri < (int) posi.size())
        {
            while(lo < (int) poso.size() && poso[lo] < posj[j]) lo++;
            while(ro < (int) poso.size() && (ro - lo + 1) != k) ro++;
            if(ro == (int) poso.size()) break;

            while(li < (int) posi.size() && posi[li] < poso[ro]) li++;
            while(ri < (int) posi.size() && (ri - li + 1) != k) ri++;
            if(ri == (int) posi.size()) break;

            ans = min(ans, posi[ri] - posj[j - k + 1] + 1);
            j++;
        }

        if(ans == mINF) cout << "-1\n";
        else cout << ans - k * 3 << "\n";
    }

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

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int64_t MASK(int j)
    {
        return (1LL << j);
    }

    bool BIT(int64_t tmp, int j)
    {
        return (tmp & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

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