Submission #1148114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148114		ferchostudio	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	76 ms	12648 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    static class Position {
    long x, y;

    // O(1)
    Position(long x, long y) {
      this.x = x;
      this.y = y;
    }
  }

  // O(1)
  private static long calculateDistance(Position from, Position to) {
    return Math.abs(from.x - to.x) + Math.abs(from.y - to.y); // 6 oe
  }

  // T(n) = 12 + 2N(9) + 5 + N(13) + 9 + 2N(9 + 2N(14) + 4 + 2 + 2) + 1
  // T(n) = 27 + 18N + 13N + 2N(17 + 28N)
  // T(n) = 27 + 31N + 34N + 56N^2
  // O(N^2)
  public static long minMovesToTarget(int N, long[][] coins) {
    Position[] coinPositions = new Position[2 * N]; // 4 oe
    Position[] targets = new Position[2 * N]; // 4 oe

    for (int i = 0; i < 2 * N; i++) {
      // 2 oe + 2 oe + 2 oe
      coinPositions[i] = new Position(coins[i][0], coins[i][1]); // 5 oe
    }

    int idx = 0; // 2 oe
    for (int x = 1; x <= N; x++) {
      // 2 oe + 1 oe + 2 oe
      targets[idx++] = new Position(x, 1); // 5 oe
      targets[idx++] = new Position(x, 2); // 5 oe
    }

    boolean[] usedTarget = new boolean[2 * N]; // 3 oe
    long totalMoves = 0; // 2 oe

    for (int i = 0; i < 2 * N; i++) {
      // 2 oe + 2 oe + 2 oe
      long minDist = Long.MAX_VALUE; // 2 oe
      int bestTarget = -1; // 2 oe

      for (int j = 0; j < 2 * N; j++) {
        // 2 oe + 2 oe + 2 oe
        if (!usedTarget[j]) { // 2 oe
          long dist = calculateDistance(coinPositions[i], targets[j]); // 5 oe
          if (dist < minDist) { // 1 oe
            minDist = dist; // 1 oe
            bestTarget = j; // 1 oe
          }
        }
      }

      usedTarget[bestTarget] = true; // 2 oe
      totalMoves += minDist; // 2 oe
    }

    return totalMoves; // 1 oe
  }

  // T(n) = 9 + 2 + 2 + 2N(6 + 4) + 1 + N^2 + 1
  // T(n) = 15 + 20N + N^2
  // T(n) = 15 + 20N + N^2
  // O(N^2)
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in); // 3 oe
    int N = scanner.nextInt(); // 3 oe
    long[][] coins = new long[2 * N][2]; // 3 oe

    for (int i = 0; i < 2 * N; i++) {
      // 2 oe + 2 oe + 2 oe
      coins[i][0] = scanner.nextLong(); // 3 oe
      coins[i][1] = scanner.nextLong(); // 3 oe
    }

    System.out.println(minMovesToTarget(N, coins)); // 1 oe + O(N^2)
    scanner.close(); // 1 oe
  }
}

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