COCI 2019/2020 - Contest 3 - Drvca

View as PDF

Submit solution

Points: 1.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 3
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Advent in Zagreb là một ngày lễ truyền thống, nổi bật nhất là một hội chợ Giáng Sinh kì diệu nằm giữa trung tâm thành phố. Sự kiện này còn được bình chọn là tuyệt nhất châu Âu trong vòng 3 năm liên tiếp. Tiếng lành không chỉ lan nhanh mà còn rất xa. Thật vậy, thông tin về Advent in Zagreb đã tới Bắc Cực và đến tai của ông già Noel. Thú vị thay, ông già Noel thì chưa bao giờ từng đi tới Croatia (ngoại trừ công việc bình thường vào mỗi đêm Giáng Sinh). Có thể thấy rằng, ông ấy không thích những hoạt động mùa hè ở bờ biển. Thay vì thế ông ấy có thể thoải mái ngồi giải những bài tập COCI ở nhà.

May mắn thay, ông đã quyết định ghé thăm hội chợ Giáng Sinh của chúng ta. Ông ấy đã gửi 1 bức thư tới tòa nhà thị chính, nói rằng ông ấy sẽ đáp xuống quảng trường Zagreb vào sáng sớm ngày 14 tháng 12. Sau lần tham gia tại nhà ở 1 vòng đấu COCI, ông ấy sẽ được ông Malnar dẫn đi thăm quan những địa điểm ấm thực ngon nhất của Zagreb.

Bạn có lẽ đang tự hỏi: Ông già Noel sẽ dự định đáp xuống như thế nào, khi ở đó không có đường băng? Chính xác là không có đường băng nào, nhưng chúng ta sẽ xử lí nó.

Thị trấn đã chuẩn bị ~N~ cây thông Giáng Sinh, đặt ở quảng trường chính. Giờ, họ sẽ lấy những cây thông đó và đặt nó vào ~2~ hàng để tạo thành ranh giới của đường băng. Vì một vài lí do, mà họ muốn sự chệnh lệch tuyệt đối về chiều cao giữa ~2~ cây cạnh nhau ở cùng 1 hàng là bằng nhau. Hơn nữa, các cây trong cùng ~1~ hàng phải được xếp theo chiều cao, từ thấp nhất tới cao nhất.

Hãy giúp họ chia những cái cây thành ~2~ hàng thỏa mãn các điều kiện trên.

Input

Dòng đầu tiên chứa số ~N~ ~(2 \le N \le 10^5)~ như trong đề bài đã mô tả.

Dòng tiếp theo chứa ~N~ số nguyên ~Hi~ ~(1 \le H_i \le 10^9)~ mô tả chiều cao của ~N~ cây thông Noel.

Output

Dòng đầu tiên, in ra số nguyên ~A~ là số cây ở hàng đầu tiên.

Dòng thứ hai, in ra ~A~ số nguyên biểu diễn chiều cao của các cây ở hàng đầu tiên của đường băng.

Dòng thứ ba, in ra số nguyên ~B~ là số cây ở hàng thứ hai.

Dòng thứ tư, in ra ~B~ số nguyên biểu diễn chiều cao của các cây ở hàng thứ hai của đường băng

~~

Các hàng không được phép không có cây ~(A > 0~ và ~B > 0)~ và mỗi cây phải nằm trong ~1~ hàng ~(A + B = N)~ .

Hơn nữa, các cây trong mỗi hàng phải được sắp xếp theo độ cao tăng dần.

Nếu có nhiều đáp án, in ra 1 đáp án bất kì trong số đó. Nếu không có đáp án nào thỏa mãn, in ra ~-1~

Sample Input 1

4
1 2 3 4

Sample Output 1

2
1 2
2 
3 4

Sample Input 2

6 
23 4 7 6 8 15

Sample Output 2

3 
4 6 8 
3 
7 15 23

Sample Input 3

6 
1 2 3 7 9 10

Sample Output 3

-1

Subtask

  • ~14~ test đầu tiên có ~N \le 15~
  • ~18~ test tiếp theo có ~N \le 300~
  • ~12~ test tiếp theo có ~N \le 10^5~ và có 1 đáp án mà cả ~2~ hàng có cùng số lượng cây
  • ~16~ test còn lại không có ràng buộc gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.