trang chủ / đề bài / icpc23_reg_g

Gameshow thời trang

Đề bài

Mô tả

Chính thức rồi! Tổ chức VNOI (Vietnamese National Outfit Innovation) được chọn đăng cai Glamorous Garment Gameshow 2023. Hứa hẹn là một sự kiện rực rỡ, chương trình sẽ được truyền hình trực tiếp tới hàng triệu khán giả tại Việt Nam. Cuộc thi có 2n thí sinh tài năng, được các nhà thiết kế nổi tiếng của Việt Nam đánh giá qua nhiều vòng đấu căng thẳng. Thí sinh thứ i có chỉ số sức mạnh si, được tính từ nhiều yếu tố như độ nổi tiếng trên mạng xã hội, lượng người hâm mộ, thậm chí cả tốc độ di chuột, ...

Vòng sơ loại gồm hai lượt. Ở mỗi lượt, các thí sinh được chia thành n cặp và thi đấu thiết kế đối đầu một chọi một. Để giữ sự hấp dẫn, hai thí sinh đã gặp nhau ở lượt thứ nhất sẽ không gặp lại nhau ở lượt thứ hai.

Nói một cách toán học, gọi ai và bi lần lượt là đối thủ của thí sinh thứ i ở lượt thứ nhất và lượt thứ hai. Với mọi 1≤i≤2n, các điều kiện sau phải được thoả mãn:

  • ai≠i;
  • bi≠i;
  • ai≠bi;
  • i=aai=bbi.

Ban tổ chức muốn tạo ra các trận đấu hấp dẫn bằng cách ghép các thí sinh có chỉ số sức mạnh chênh lệch ít nhất. Nói cách khác, họ muốn cực tiểu hoá

maxi=1…2n{max(|si−sai|,|si−sbi|)}.

Cho chỉ số sức mạnh của tất cả các thí sinh, hãy ghép cặp các thí sinh cho hai lượt của vòng sơ loại sao cho đại lượng trên nhỏ nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên n (2≤n≤2·105).
  • Dòng thứ hai chứa 2n số nguyên s1,s2,…,s2n (1≤si≤109): chỉ số sức mạnh của các thí sinh. Các thí sinh được đánh số từ 1 đến 2n.

Dữ liệu vào kết thúc bởi một dòng chứa duy nhất số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu bảo đảm tổng n của tất cả các bộ dữ liệu không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

  • Dòng thứ nhất chứa 2n số nguyên a1,a2,…,a2n (1≤ai≤2n): đối thủ của các thí sinh ở lượt thứ nhất.
  • Dòng thứ hai chứa 2n số nguyên b1,b2,…,b2n (1≤bi≤2n): đối thủ của các thí sinh ở lượt thứ hai.

Nếu có nhiều cách ghép tối ưu, in ra cách bất kỳ.

Ràng buộc

  • 2≤n≤2·105, tổng n không vượt quá 2·105
  • 1≤si≤109

Ví dụ

Input Output Giải thích
2
1 2 3 4
0
2 1 4 3
3 4 1 2
Lượt một: cặp (1,2) và (3,4), chênh lệch đều là 1. Lượt hai: cặp (1,3) và (2,4), chênh lệch đều là 2. Đại lượng cần cực tiểu bằng 2, và đây là giá trị nhỏ nhất có thể.
3
5 5 5 5 5 5
4
1 100 2 101 3 102 4 103
2
7 7 7 7
0
3 4 1 2 6 5
2 1 5 6 3 4
5 6 7 8 1 2 3 4
3 4 1 2 7 8 5 6
3 4 1 2
2 1 4 3
Ví dụ bổ sung. Bộ thứ hai: các thí sinh 1,3,5,7 (sức mạnh 1..4) chỉ đấu với nhau, các thí sinh 2,4,6,8 (sức mạnh 100..103) cũng vậy; chênh lệch lớn nhất là 2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0