trang chủ / đề bài / icpc22_reg_c

Đổi chỗ ngồi

Đề bài

Mô tả

Kỳ thi Lập trình Sinh viên Quốc tế (ICPC) là cuộc thi mà các thí sinh tham gia theo đội. Cuộc thi không chỉ thử thách kỹ năng thuật toán và kỹ năng giải quyết vấn đề của thí sinh mà còn đòi hỏi sự phối hợp và đoàn kết giữa các thành viên trong đội.

Hôm nay, bên cạnh sự kiện chính, các thí sinh ICPC còn có cơ hội tham gia một trò chơi nhỏ. Có tổng cộng 2·n−1 người tham gia, ban tổ chức chuẩn bị 2·n chiếc ghế, xếp thành hai hàng, mỗi hàng n ghế. Hai hàng ghế đối diện nhau, các ghế trên mỗi hàng được đánh số từ 1 đến n từ trái sang phải, nên ghế thứ i của hàng thứ nhất đối diện với ghế thứ i của hàng thứ hai. Người chơi được đánh số từ 1 đến 2·n−1.

Ban đầu, mỗi người chọn một ghế để ngồi. 2·n−1 người ngồi trên 2·n−1 ghế khác nhau, nên có đúng một ghế trống. Trò chơi diễn ra như sau: ở mỗi lượt, mọi người bầu chọn một người đang ngồi ở hàng không chứa ghế trống. Người được chọn sẽ di chuyển sang ghế trống.

Mục tiêu của trò chơi là sau không quá 686868 lượt, các điều kiện sau được thỏa mãn:

  • Người ban đầu ngồi ở ghế thứ i của hàng thứ nhất bây giờ ngồi ở ghế thứ i của hàng thứ hai.
  • Người ban đầu ngồi ở ghế thứ i của hàng thứ hai bây giờ ngồi ở ghế thứ i của hàng thứ nhất.

Dù là một trò chơi đơn giản, nó vẫn rất thử thách. Để thắng, mọi người phải hợp tác với nhau. Là một thành viên trong đội, bạn cũng muốn góp sức! Cho cách ngồi ban đầu, hãy tìm một cách để mọi người thắng trò chơi, hoặc cho biết không thể đạt được mục tiêu.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤105) là số ghế trên mỗi hàng.
  • Dòng thứ i trong hai dòng tiếp theo chứa n số nguyên ai,1,ai,2,…,ai,n (0≤ai,j<2·n) mô tả cách ngồi ban đầu: nếu ai,j>0 thì ai,j là số hiệu người ngồi ở ghế thứ j của hàng thứ i; ngược lại, ghế thứ j của hàng thứ i trống.

Dữ liệu đảm bảo các giá trị ai,j đôi một khác nhau.

Dữ liệu ra

Nếu không có cách nào thắng trò chơi, in ra một số nguyên −1.

Ngược lại, dòng đầu tiên in số nguyên m (0≤m≤686868) là số lượt cần dùng. Dòng tiếp theo in m số nguyên b1,b2,…,bm (1≤bi<2·n), trong đó bi là số hiệu người di chuyển sang ghế trống ở lượt thứ i.

Nếu có nhiều cách, in ra cách bất kỳ.

Ràng buộc

  • 1≤n≤105
  • 0≤ai,j<2·n, các giá trị đôi một khác nhau

Ví dụ

Input Output Giải thích
1
1
0
1
1
Người 1 chuyển từ hàng thứ nhất sang ghế trống đối diện.
3
2 0 1
3 5 4
11
3 2 5 3 4 5 3 4 5 1 4
Sau 11 lượt, hàng thứ nhất là 3,5,4 và hàng thứ hai là 2,0,1. Đây chỉ là một đáp án đúng, còn nhiều đáp án khác.
2
1 2
3 0
-1 Ví dụ bổ sung (không có trong đề gốc): với n=2 không thể thắng trò chơi.

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