Bedao Regular Contest 03 - RACE

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Như ai cũng biết, chị Hiền là một con người ác độc và có những trò chơi cũng tàn nhẫn không kém tâm hồn chị. Năm nay, cũng như mọi lần, chị Hiền lại tổ chức giải "Đua chó mở rộng", cuộc đua diễn ra trên trục tọa độ ~Oxy~.

Ban đầu, có ~n~ chú chó (bao gồm đủ loại màu sắc chứ không chỉ màu vàng) sẽ tham gia cuộc thi và đứng ở vạch xuất phát (~x = 0~). Về mặt toán học, ta sẽ biểu diễn vị trí đứng của ~n~ chú chó này bằng một mảng ~p~ độ dài ~n~. Chú chó thứ ~i~ sẽ xuất phát ở điểm có tọa độ ~(0, p_i)~.

Đồng thời do chị Hiền không thích việc hai chú chó cắn nhau trước khi chạy đua, dữ liệu đảm bảm rằng mọi vị trí ~p_i~ đều phân biệt. Vạch kết thúc là ~x = k~.

Chó vàng là một trong những dân bet đua chó dạng trùm sỏ, vì thế anh ấy đã bí mật thao túng cuộc thi này. Bây giờ, việc gọi đây là một giải đua chó cũng không hẳn là đúng, vì thật ra mọi chú chó đều sẽ có tốc độ giống nhau!! Sốc hơn nữa, mọi chú chó sẽ không chạy theo đường thẳng, mà sẽ chỉ chạy theo đường chéo về đích. Về mặt toán học, giả sử chú chó thứ ~i~ được phân loại ~t_i~ (với ~t_i~ bằng ~-1~ hoặc ~1~). Nếu:

  • ~t_i = -1~, thì chú chó thứ ~i~ sẽ có vận tốc là ~(1, -1)~ trên giây.
  • ~t_i = 1~, thì chú chó thứ ~i~ sẽ có vận tốc là ~(1, 1)~ trên giây.

Với một cuộc đua bất công như thế này, va chạm giữa hai "chó thủ" là điều hoàn toàn có thể xảy ra. Vì thế, trước khi bắt đầu, mọi chú chó đã thỏa thuận với nhau cách để xử lí khi có một cặp chó va chạm: hai chú chó va chạm sẽ hoán đổi vận tốc cho nhau. Về mặt toán học, giả sử chó chó ~A~ có loại ~1~ va chạm với chú chó ~B~ có loại ~-1~, thì ngay sau khi va chạm, loại của chú chó ~A~ sẽ trở thành ~-1~, và loại của chú chó ~B~ sẽ trở thành ~1~.

Bạn là người quản lý cuộc đua, để tổng hợp để xem trong cuộc đua có sự bán độ hay không, bạn cần biết hai thông tin sau khi cuộc thi kết thúc:

  • Số lượng va chạm đã diễn ra trong cuộc thi ngay trước khi mọi chú chó cán đích. Điều này có nghĩa là va chạm giữa những chú chó trên vạch kết thúc sẽ không được tính.

  • Vị trí kết thúc của từng chú chó từ ~1~ đến ~n~.

Input

  • Dòng đầu tiên gồm hai số nguyên phân biệt ~n~ và ~k~ (~1 \le n \le 200\,000~, ~1 \le k \le 10^9~) - lần lượt là số lượng chú chó tham gia cuộc thi và tọa độ ~x~ của vạch kết thúc.
  • Dòng thứ hai gồm ~n~ số nguyên ~p_1, p_2, \cdots, p_n~ (~-10^9 \le y_i \le 10^9~) - biểu diễn tọa độ ~y~ của ~n~ chú chó trên vạch xuất phất. Dữ liệu đảm bảo rằng mọi ~p_i~ đều phân biệt, hay nói cách khác, ~p_i \ne p_j~ với mọi ~1 \le i < j \le n~.
  • Dòng thư ba gồm ~n~ số nguyên ~t_1, t_2, \cdots, t_n~ (~t_i \in \{-1, 1\}~) - biểu diễn loại của ~n~ chú chó.

Output ra

Bạn cần in ra hai dòng:

  • Dòng thứ nhất chứa một số nguyên duy nhất - số lượng va chạm đã diễn ra trong cuộc thi ngay trước khi mọi chú chó cán đích.
  • Dòng thứ hai chứa ~n~ số nguyên, số nguyên thứ ~i~ biểu diễn tọa độ ~y_i~ là vị trí cán đích của chú chó thứ ~i~.

Sample Input

3 2
1 0 2
1 1 -1

Sample Output

2
2 0 3

Sample Input

2 1
0 2
1 -1

Sample Output

0
1 1

Hình vẽ mô tả test ví dụ 1, đường màu đỏ biểu diễn đường đi của chú chó thứ ~1~, đường màu xanh lam của chú chó thứ ~2~, đường màu xanh lục của chú chó thứ ~3~. Những điểm màu đen biểu diễn va chạm đã xảy ra.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.