Đài Loan có một hệ thống đường tàu lớn nối hai bờ đông và tây của hòn đảo. Hệ thống gồm \(m\) khối liên tiếp, được đánh số \(0, \ldots, m-1\) bắt đầu từ đầu phía tây. Mỗi khối có một tuyến đường một chiều ở phía bắc đi về hướng tây, một tuyến đường một chiều ở phía nam đi về hướng đông, và có thể có một ga tàu nằm giữa hai tuyến đường.

Có ba loại khối:

• Khối loại C chứa một ga tàu mà bạn phải đi vào từ tuyến phía bắc và đi ra tuyến phía nam.
• Khối loại D chứa một ga tàu mà bạn phải đi vào từ tuyến phía nam và đi ra tuyến phía bắc.
• Khối loại trống không chứa ga tàu.

Ví dụ, trong hình dưới đây, các khối 0, 4 và 6 thuộc loại trống, các khối 1, 2 và 3 thuộc loại C, còn khối 5 thuộc loại D. Các khối nối với nhau theo chiều ngang. Các tuyến tương ứng của hai khối liền kề được nối bởi các điểm nối, được minh họa bằng những hình chữ nhật tô mờ.

Hệ thống có \(n\) ga tàu, được đánh số từ \(0\) đến \(n-1\). Có thể giả thiết rằng ta có thể đi từ bất kỳ ga tàu nào đến bất kỳ ga tàu nào khác bằng cách đi theo tuyến đường. Ví dụ, để đi từ ga 0 đến ga 2, ta xuất phát từ khối 2, đi qua các khối 3 và 4 theo tuyến phía nam, đi qua ga 1 ở khối 5, rồi đi qua khối 4 theo tuyến phía bắc và cuối cùng đến ga 2 ở khối 3.

Vì có thể có nhiều đường đi, khoảng cách từ một ga đến một ga khác được định nghĩa là số lượng nhỏ nhất các điểm nối mà đường đi phải đi qua. Trong ví dụ, đường đi ngắn nhất từ ga 0 đến ga 2 đi qua các khối sau:

2-3-4-5-4-3

Đường đi này đi qua 5 điểm nối, nên khoảng cách là 5.

Hệ thống đường tàu được quản lý bởi máy tính. Không may, sau một sự cố mất điện, máy tính không còn biết các ga nằm ở đâu và nằm trong loại khối nào. Manh mối duy nhất còn lại là số thứ tự của khối chứa ga 0; khối này luôn thuộc loại C. May mắn là máy tính vẫn có thể truy vấn khoảng cách từ một ga bất kỳ đến một ga bất kỳ khác. Chẳng hạn, truy vấn “Khoảng cách từ ga 0 đến ga 2 là bao nhiêu?” sẽ nhận được giá trị 5.

Nhiệm vụ

Bạn cần cài đặt hàm findLocation(n, first, location, stype) để xác định số thứ tự khối và loại khối chứa mỗi ga tàu.

• n: số lượng ga tàu.
• first: số thứ tự khối chứa ga 0.
• location: mảng độ dài \(n\); bạn cần gán số thứ tự khối chứa ga \(i\) vào location[i].
• stype: mảng độ dài \(n\); bạn cần gán loại khối chứa ga \(i\) vào stype[i]: 1 cho loại C và 2 cho loại D.

Bạn có thể gọi hàm getDistance(i, j) để xác định vị trí và loại khối của các ga. Hàm trả về khoảng cách từ ga i đến ga j. getDistance(i, i) trả về 0. getDistance(i, j) trả về -1 nếu i hoặc j nằm ngoài phạm vi từ \(0\) đến \(n-1\).

Các subtasks

Trong tất cả các subtasks, số khối \(m\) không lớn hơn \(1\,000\,000\). Một số subtasks giới hạn số lần gọi getDistance; giới hạn tùy thuộc subtask. Chương trình nhận kết quả wrong answer nếu vượt quá giới hạn này.

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên rail.c, rail.cpp hoặc rail.pas, cài đặt findLocation theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề rail.h.

C/C++:

void findLocation(int n, int first, int location[], int stype[]);

Pascal:

procedure findLocation(n, first : longint; var location,
stype : array of longint);

Hàm getDistance có chữ ký như sau.

C/C++:

int getDistance(int i, int j);

Pascal:

function getDistance(i, j: longint): longint;

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: số thứ tự subtask.
• Dòng 2: n.
• Dòng \(3+i\), với \(0 \le i \le n-1\): stype[i] (1 cho loại C, 2 cho loại D), rồi location[i].

Khi findLocation trả về, trình chấm mẫu in Correct nếu toàn bộ location[0] ... location[n-1] và stype[0] ... stype[n-1] do chương trình tính được khớp với dữ liệu vào; nếu không khớp, nó in Incorrect.