Submission #1146825

#TimeUsernameProblemLanguageResultExecution timeMemory
1146825carolCoin Collecting (JOI19_ho_t4)Java
0 / 100
90 ms13444 KiB
import java.util.*;

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 State {
        Point position;
        int distance;
        
        State(Point position, int distance) {
            this.position = position;
            this.distance = distance;
        }
    }
    
    // Directions for possible moves (up, right, down, left)
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Read input
        int N = scanner.nextInt();
        Point[] coins = new Point[2 * N];
        for (int i = 0; i < 2 * N; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            coins[i] = new Point(x, y);
        }
        
        // Generate target positions (1≤x≤N and 1≤y≤2)
        List<Point> targets = new ArrayList<>();
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new Point(x, y));
            }
        }
        
        // Find minimum total distance using Hungarian Algorithm approach
        long totalMoves = 0;
        boolean[] usedCoins = new boolean[2 * N];
        boolean[] usedTargets = new boolean[2 * N];
        
        // For each target position
        for (int i = 0; i < 2 * N; i++) {
            int minDist = Integer.MAX_VALUE;
            int selectedCoin = -1;
            int selectedTarget = -1;
            
            // Find the closest unused coin to any unused target
            for (int j = 0; j < 2 * N; j++) {
                if (usedCoins[j]) continue;
                
                for (int k = 0; k < 2 * N; k++) {
                    if (usedTargets[k]) continue;
                    
                    int dist = calculateDistance(coins[j], targets.get(k));
                    if (dist < minDist) {
                        minDist = dist;
                        selectedCoin = j;
                        selectedTarget = k;
                    }
                }
            }
            
            // Mark the coin and target as used and add the distance
            usedCoins[selectedCoin] = true;
            usedTargets[selectedTarget] = true;
            totalMoves += minDist;
        }
        
        System.out.println(totalMoves);
    }
    
    // Calculate minimum moves between two points using Manhattan distance
    private static int calculateDistance(Point start, Point end) {
        return Math.abs(start.x - end.x) + Math.abs(start.y - end.y);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...