1
class SORTracker {
2

3
  private TreeMap<Integer, List<String>> map;
4
  private int queryNum;
5

6
  // Find suitable position for name in the list
7
  private int getIndex(String name, List<String> list) {
8
    int l = 0, r = list.size() - 1, m = 0;
9
    while (l < r) {
10
      m = l + (r - l) / 2;
11
      if (name.compareTo(list.get(m)) > 0) {
12
        l = m + 1;
13
      } else {
14
        r = m;
15
      }
16
    }
17
    return name.compareTo(list.get(l)) > 0 ? l + 1 : l;
18
  }
19

20
  public SORTracker() {
21
    map = new TreeMap<>((a, b) -> (b - a));
22
    queryNum = 0;
23
  }
24

25
  public void add(String name, int score) {
26
    List<String> list = map.getOrDefault(score, new ArrayList<>());
27
    int index = (list.size() == 0) ? 0 : getIndex(name, list);
28
    list.add(index, name);
29
    map.put(score, list);
30
  }
31

32
  public String get() {
33
    int index = queryNum;
34
    for (int score : map.keySet()) {
35
      if (index < map.get(score).size()) {
36
        queryNum++;
37
        return map.get(score).get(index);
38
      }
39
      index -= map.get(score).size();
40
    }
41
    return "";
42
  }
43
}