oj.uz

Submission #770650

# Submission time Handle Problem Language Result Execution time Memory
770650 2023-07-01T15:07:32 Z nihon JJOOII 2 (JOI20_ho_t2) C++14
100 / 100
 11 ms 1616 KB 
#include <bits/stdc++.h>
#define N 200005
using namespace std;
string s;
char ch;
int n,k,i,l,st,dr,mid,sol,b,e,x;
int J[N],O[N],I[N],tj,to,ti;
int mn=2e9;
int main()
{
    cin>>n>>k>>s;
    l=s.size();
    for(i=0;i<l;i++)
    {
        ch=s[i];
        if(ch=='J')
        {
            J[++tj]=i;
        }
        if(ch=='O')
        {
            O[++to]=i;
        }
        if(ch=='I')
        {
            I[++ti]=i;
        }
    }
    for(i=1;i<=tj;i++)
    {
        if(i+k-1>tj) break;
        b=J[i];
        x=J[i+k-1]+1;
        if(x>=l) continue;
        st=1; dr=to; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(O[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>to) continue;
        x=O[sol+k-1]+1;
        if(x>=l) continue;
        st=1; dr=ti; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(I[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>ti) continue;
        e=I[sol+k-1];
        mn=min(mn,(e-b+1)-3*k);
    }
    if(mn==2e9) cout<<-1;
    else cout<<mn;
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 308 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 304 KB Output is correct
36 Correct 9 ms 1488 KB Output is correct
37 Correct 10 ms 1540 KB Output is correct
38 Correct 11 ms 1508 KB Output is correct
39 Correct 9 ms 1516 KB Output is correct
40 Correct 9 ms 1616 KB Output is correct
41 Correct 9 ms 1508 KB Output is correct
42 Correct 10 ms 1568 KB Output is correct
43 Correct 5 ms 1124 KB Output is correct
44 Correct 6 ms 1252 KB Output is correct
45 Correct 7 ms 1616 KB Output is correct
46 Correct 7 ms 1616 KB Output is correct
47 Correct 7 ms 1508 KB Output is correct
48 Correct 7 ms 1616 KB Output is correct
49 Correct 5 ms 1124 KB Output is correct
50 Correct 7 ms 1508 KB Output is correct
51 Correct 7 ms 1612 KB Output is correct
52 Correct 5 ms 1508 KB Output is correct
53 Correct 5 ms 1616 KB Output is correct
54 Correct 6 ms 1508 KB Output is correct
55 Correct 5 ms 1508 KB Output is correct
56 Correct 4 ms 1508 KB Output is correct