Submission #1118648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118648		secretwood01	JJOOII 2 (JOI20_ho_t2)	Java	13 / 100	2033 ms	30736 KiB

ho_t2

import java.util.*;
import java.io.*;

public class ho_t2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        TreeSet<Integer> Js, Is, Os;
        Js = new TreeSet<Integer>();Is = new TreeSet<Integer>();Os = new TreeSet<Integer>();
        st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        for (int i=0;i<N;i++) {
            char c = S.charAt(i);
            if (c=='J') Js.add(i);
            else if (c=='I') Is.add(i);
            else Os.add(i);
        }
        int ans = Integer.MAX_VALUE;
        int iterations = 0;
        if (Js.size()>0) {
            int right = -1;
            int left = Js.pollFirst();
            int nLeft = next(Js, K-1, left);
            if (nLeft>=0) {
                int nnLeft = next(Os, K, nLeft);
                if (nnLeft>0) {
                    right = next(Is, K, nnLeft);
                }
            }
            if (right>0) ans = Math.min(ans, right-left+1-(3*K));
            while (right>0 && Js.size()>0&&iterations<50000) {
                left = Js.pollFirst();
                right = -1;
                int nL = next(Js, K-1, left);
                if (nL>=0) {
                    int nnL = next(Os, K, nL);
                    if (nnL>0) {
                        right = next(Is, K, nnL);
                    }
                }
                if (right>0) ans = Math.min(ans, right-left+1-(3*K));
                iterations++;
            } 
        } 
        if (ans==Integer.MAX_VALUE) ans = -1;
        pw.println(ans);
        pw.close();
        br.close();
    }
    public static int next(TreeSet<Integer> s, int n, int curr) {
        int counter = Math.min(n, 40000);
        int toReturn = curr;
        while (counter>0 && s.higher(toReturn)!=null) {
            toReturn = s.higher(toReturn);
            counter--; 
        }
        if (counter>0) return -1;
        return toReturn;
    }
}

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