oj.uz

Submission #754946

# Submission time Handle Problem Language Result Execution time Memory
754946 2023-06-09T03:35:42 Z abysmal JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 6 ms 2104 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 0 ms 320 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 324 KB Output is correct
30 Correct 1 ms 320 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 0 ms 320 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 324 KB Output is correct
30 Correct 1 ms 320 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 4 ms 1612 KB Output is correct
37 Correct 5 ms 1808 KB Output is correct
38 Correct 5 ms 1956 KB Output is correct
39 Correct 5 ms 1956 KB Output is correct
40 Correct 4 ms 2008 KB Output is correct
41 Correct 5 ms 1940 KB Output is correct
42 Correct 6 ms 1824 KB Output is correct
43 Correct 2 ms 1268 KB Output is correct
44 Correct 3 ms 1496 KB Output is correct
45 Correct 4 ms 2104 KB Output is correct
46 Correct 4 ms 1988 KB Output is correct
47 Correct 4 ms 1980 KB Output is correct
48 Correct 5 ms 2008 KB Output is correct
49 Correct 3 ms 1336 KB Output is correct
50 Correct 4 ms 1996 KB Output is correct
51 Correct 4 ms 2008 KB Output is correct
52 Correct 3 ms 1476 KB Output is correct
53 Correct 4 ms 1740 KB Output is correct
54 Correct 3 ms 2040 KB Output is correct
55 Correct 2 ms 1988 KB Output is correct
56 Correct 3 ms 2012 KB Output is correct