Submission #227502

#	Time	Username	Problem	Language	Result	Execution time	Memory
227502		Bruteforceman	Sky Walking (IOI19_walk)	Java	10 / 100	4543 ms	175788 KiB

walk

import java.math.*;
import java.util.*;
class walk {
  class Pair implements Comparator <Pair> {
    int first, second;
    Pair () {}
    Pair (int first, int second) {
      this.first = first; this.second = second;
    }
    public int compare(Pair a, Pair b) {
      if(a.first == b.first) return a.second - b.second;
      return a.first - b.first;
    }
  }
  class Node implements Comparator <Node> {
    long dist;
    int pos, line;
    Node () {}
    Node (long dist, int pos, int line) {
      this.dist = dist; this.pos = pos; this.line = line;
    }
    public int compare(Node a, Node b) {
      if(a.dist != b.dist) return Long.compare(a.dist, b.dist);
      if(a.pos != b.pos) return a.pos - b.pos;
      return a.line - b.line;
    }
  }
	public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int f, int g) {
    int n = x.length;
    int m = y.length;
    TreeSet <Pair> [] s = new TreeSet [n];
    for(int i = 0; i < n; i++) {
      s[i] = new TreeSet <> (new Pair());
    }
    for(int i = 0; i < m; i++) {
      for(int j = l[i]; j <= r[i]; j++) {
        if(y[i] <= h[j]) {
          s[j].add(new Pair(y[i], i));
        }
      }
    }
    s[f].add(new Pair(0, m));
    s[g].add(new Pair(0, m + 1));

    TreeMap <Pair, Long> dist = new TreeMap <> (new Pair());
    TreeSet <Node> q = new TreeSet <> (new Node());
    q.add(new Node(0L, f, m));
    dist.put(new Pair(f, m), 0L);
    while(!q.isEmpty()) {
      int pos = q.first().pos;
      int line = q.first().line;
      long current = q.first().dist;
      q.remove(new Node(current, pos, line));
      int high = (line >= m) ? 0 : y[line];
      if(dist.get(new Pair(pos, line)) != current) continue;

      // System.out.println(pos + " " + line + " " + current);

      ArrayList <Pair> can = new ArrayList <> ();
      if(line < m) {
        for(int j = pos + 1; j <= r[line]; j++) {
          if(h[j] >= high) {
            can.add(new Pair(j, line));
            break;
          }
        }
        for(int j = pos - 1; j >= l[line]; j--) {
          if(h[j] >= high) {
            can.add(new Pair(j, line));
            break;
          }
        }
      }
      Pair a = s[pos].lower(new Pair(high, line));
      Pair b = s[pos].higher(new Pair(high, line));
      if(a != null) {
        can.add(new Pair(pos, a.second));
      }
      if(b != null) {
        can.add(new Pair(pos, b.second));
      }
      for(Pair i : can) {
        int nxtH = (i.second >= m) ? 0 : y[i.second];
        long d = current + Math.abs(x[pos] - x[i.first]) + 
          Math.abs(high - nxtH);
      //  System.out.println(i.first + " and " + i.second + " = " + d);
        if(dist.get(i) == null || dist.get(i) > d) {
          dist.put(new Pair(i.first, i.second), d);
          q.add(new Node(d, i.first, i.second));
        }
      }
    }
		return dist.get(new Pair(g, m + 1)) == null ? -1 : dist.get(new Pair(g, m + 1));
	}
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43