Submission #1138101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138101		secretwood01	Take-out (POI13_usu)	Java	0 / 100	757 ms	131072 KiB

usu

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

public class usu {
    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());
        st = new StringTokenizer(br.readLine());
        char [] a = st.nextToken().toCharArray();
        TreeMap<Integer, Ans> ans = new TreeMap<>();
        TreeSet<Integer> used = new TreeSet<>();
        for (int i=0;i<N;i++) {
            if (a[i]=='c') {
                ans.put(i, new Ans(i));
            }
        }
        for (int x : ans.keySet()) {
            if (x==ans.firstKey()) ans.get(x).prev = -1;
            else ans.get(x).prev = ans.lowerKey(x);
        } 
        int currclosest = ans.firstKey();
        for (int i=0;i<N;i++) {
            if (a[i]=='c') {
                currclosest = i;
                continue;
            }
            int ogc = currclosest;
            while (ans.get(currclosest).set.size()>=k+1) {
                used.add(currclosest);
                currclosest = ans.get(currclosest).prev;
                if (currclosest==-1) currclosest = ans.higherKey(used.last());
            }
            ans.get(currclosest).set.add(i);
        }
        Ans [] print = new Ans[ans.size()];
        int ind = 0;
        for (int x : ans.keySet()) {
            print[ind] = ans.get(x);
            ind++;
        }
        Arrays.sort(print);
        for (Ans x : print) {
            pw.println(x.toString());
        }
        pw.close();
        br.close();
    }
}
class Ans implements Comparable<Ans> {
    TreeSet<Integer> set;
    int dif;
    int prev;
    public Ans(int i) {
        set = new TreeSet<>();
        set.add(i);
    }
    public void calcDif() {
        dif = set.last()-set.first();
    }
    public int compareTo(Ans a) {
        this.calcDif();
        a.calcDif();
        return Integer.compare(a.dif, dif);
    }
    public String toString() {
        TreeSet<Integer> dup = (TreeSet<Integer>)set.clone();
        String S = "";
        while (dup.size()>1) {
            S+=(dup.pollFirst()+1)+" ";
        }
        S+=(dup.pollFirst()+1);
        return S;
    }
}

Compilation message (stderr)

Note: usu.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 12