Submission #1147253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147253		lucianaft	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	72 ms	12612 KiB

joi2019_ho_t4

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

public class joi2019_ho_t4 {
  static class Point {
    int x, y;

    Point(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (!(o instanceof Point)) return false;
      Point point = (Point) o;
      return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x, y);
    }
  }

  static class Assignment {
    int coin;
    Point target;
    int distance;

    Assignment(int coin, Point target, int distance) {
      this.coin = coin;
      this.target = target;
      this.distance = distance;
    }
  }

  public static int solve(int n, int[] x, int[] y) {
    List<Point> sources = new ArrayList<>();
    for (int i = 0; i < 2 * n; i++) {
      sources.add(new Point(x[i], y[i]));
    }

    List<Point> targets = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
      targets.add(new Point(i, 1));
      targets.add(new Point(i, 2));
    }

    List<Assignment> assignments = new ArrayList<>();
    for (int i = 0; i < sources.size(); i++) {
      for (Point target : targets) {
        int distance = manhattanDistance(sources.get(i), target);
        assignments.add(new Assignment(i, target, distance));
      }
    }

    assignments.sort((a, b) -> a.distance - b.distance);

    boolean[] usedCoins = new boolean[2 * n];
    Set<Point> usedTargets = new HashSet<>();
    int totalMoves = 0;
    int assignedCoins = 0;

    for (Assignment assignment : assignments) {
      if (assignedCoins == 2 * n) break;

      if (!usedCoins[assignment.coin] && !usedTargets.contains(assignment.target)) {
        totalMoves += assignment.distance;
        usedCoins[assignment.coin] = true;
        usedTargets.add(assignment.target);
        assignedCoins++;
      }
    }

    return totalMoves;
  }

  private static int manhattanDistance(Point p1, Point p2) {
    return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    int[] x = new int[2 * n];
    int[] y = new int[2 * n];

    for (int i = 0; i < 2 * n; i++) {
      x[i] = sc.nextInt();
      y[i] = sc.nextInt();
    }

    int result = solve(n, x, y);
    System.out.println(result);
  }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63