Dynamic programming on the two cars’ most recent incidents
Let dp[a][b] be the minimum distance needed to handle all remaining incidents when car 1 most recently handled incident a and car 2 most recently handled incident b. Index 0 means the car has not handled an incident: car 1 starts at (1, 1) and car 2 at (N, N). A positive index refers to that incident’s coordinates.
Since the cars together have handled every incident through max(a, b), the next one is max(a, b) + 1. There are only two choices: assign it to car 1 or car 2. The transition adds the Manhattan distance from that car’s current position to the next incident:
dp[a][b] = 0 if max(a, b) = W
next = max(a, b) + 1
dp[a][b] = min(
distance(car 1 position(a), incident[next]) + dp[next][b],
distance(car 2 position(b), incident[next]) + dp[a][next]
)Each transition handles one more incident, so recursion reaches the terminal state; choosing the smaller of the two options preserves the minimum-cost invariant. Memoization computes each (a, b) state at most once. After computing the optimum, compare the same two costs at each step to reconstruct the assignment. Either choice is optimal on a tie; this implementation chooses car 1. When W = 0, the initial state is already terminal, so it prints cost 0 and no assignment lines. Time and space are both O(W²).
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static int n;
private static int w;
private static int[][] incidents;
private static int[][] memo;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
n = input.nextInt();
w = input.nextInt();
incidents = new int[w + 1][2];
for (int i = 1; i <= w; i++) {
incidents[i][0] = input.nextInt();
incidents[i][1] = input.nextInt();
}
memo = new int[w + 1][w + 1];
for (int i = 0; i <= w; i++) {
for (int j = 0; j <= w; j++) {
memo[i][j] = -1;
}
}
StringBuilder output = new StringBuilder();
output.append(minimumDistance(0, 0)).append('\n');
int car1Last = 0;
int car2Last = 0;
while (Math.max(car1Last, car2Last) < w) {
int next = Math.max(car1Last, car2Last) + 1;
int car1Cost = distance(1, car1Last, next)
+ minimumDistance(next, car2Last);
int car2Cost = distance(2, car2Last, next)
+ minimumDistance(car1Last, next);
if (car1Cost <= car2Cost) {
output.append(1).append('\n');
car1Last = next;
} else {
output.append(2).append('\n');
car2Last = next;
}
}
System.out.print(output);
}
private static int minimumDistance(int car1Last, int car2Last) {
if (Math.max(car1Last, car2Last) == w) return 0;
if (memo[car1Last][car2Last] != -1) return memo[car1Last][car2Last];
int next = Math.max(car1Last, car2Last) + 1;
int assignToCar1 = distance(1, car1Last, next)
+ minimumDistance(next, car2Last);
int assignToCar2 = distance(2, car2Last, next)
+ minimumDistance(car1Last, next);
memo[car1Last][car2Last] = Math.min(assignToCar1, assignToCar2);
return memo[car1Last][car2Last];
}
private static int distance(int car, int lastIncident, int nextIncident) {
int startRow = lastIncident == 0 ? (car == 1 ? 1 : n) : incidents[lastIncident][0];
int startColumn = lastIncident == 0 ? (car == 1 ? 1 : n) : incidents[lastIncident][1];
return Math.abs(startRow - incidents[nextIncident][0])
+ Math.abs(startColumn - incidents[nextIncident][1]);
}
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) return -1;
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}