trang chủ / đề bài / icpc22_reg_i

Nghịch thế

Đề bài

Mô tả

Đây là một bài toán tương tác.

Trong lúc chuẩn bị bài H. Bài khó nhất (một bài về đếm, hoán vị và nghịch thế) cho kỳ thi ICPC khu vực năm 2022, ban giám khảo phát hiện ra rằng một số lời giải chậm có thể được tối ưu rất nhiều bằng cách đổi chỗ hai phần tử bất kỳ của một hoán vị để được một hoán vị mới. Lộc, một thành viên ban giám khảo, đưa ra giả thuyết rằng nếu lời giải bằng cách nào đó duy trì được số nghịch thế mà không cần lưu hoán vị thật sự, lời giải đó sẽ chạy cực nhanh, thậm chí có thể nhanh hơn cả lời giải mẫu!

Nhưng làm sao dùng thông tin về số nghịch thế để tìm lại được hoán vị ban đầu? Để minh họa, giả sử có một hoán vị ẩn p độ dài n. Lộc nói rằng có cách tìm ra p bằng n câu hỏi có dạng sau:

  • Chọn hai chỉ số i và j (1≤i,j≤n). Số nghịch thế của p là bao nhiêu nếu đổi chỗ pi và pj?

Hiện giờ chỉ Lộc biết cách dùng các thông tin này để tìm mảng p, nên Lộc thách mọi người làm được điều tương tự!

Hoán vị ẩn p độ dài n do Lộc nắm giữ. Hãy tìm p bằng cách hỏi Lộc không quá n câu hỏi dạng trên.

Một nghịch thế của hoán vị p là một cặp (i,j) (1≤i<j≤n) sao cho pi>pj. Câu hỏi chỉ là giả định: hoán vị ẩn không thay đổi sau mỗi câu hỏi.

Dữ liệu vào

Quá trình tương tác như sau:

  • Đầu tiên, chương trình của bạn đọc một số nguyên n (1≤n≤104) là độ dài hoán vị ẩn p.
  • Tiếp theo, bạn được hỏi Lộc (chương trình chấm) không quá n câu hỏi. Để hỏi, in ra ? i j (1≤i,j≤n), rồi đọc câu trả lời là số nghịch thế của p nếu đổi chỗ pi và pj.
  • Khi đã tìm ra hoán vị p, in ra ! p1 p2 … pn và kết thúc chương trình.

Sau khi in mỗi dòng, đừng quên in ký tự xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() (hoặc endl) trong C++, sys.stdout.flush() trong Python.

Dữ liệu ra

Các câu hỏi và câu trả lời cuối cùng được in theo đúng định dạng mô tả ở trên.

Ràng buộc

  • 1≤n≤104
  • Không quá n câu hỏi.

Ví dụ

Input Output Giải thích
3
1
2
2
? 1 1
? 1 2
? 1 3
! 1 3 2
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Hoán vị ẩn là p=[1,3,2]. Đổi chỗ p1 với chính nó không làm thay đổi p, có 1 nghịch thế. Đổi chỗ p1 và p2 được [3,1,2] với 2 nghịch thế. Đổi chỗ p1 và p3 được [2,3,1] với 2 nghịch thế. Đề gốc minh họa cùng hoán vị này bằng các câu hỏi ? 1 2 (trả lời 2), ? 2 3 (trả lời 0, vì [1,2,3] không có nghịch thế), ? 3 1 (trả lời 2) rồi in ! 1 3 2.
1 ! 1 Ví dụ bổ sung: n=1, hoán vị duy nhất là [1], không cần hỏi.
2
1
0
? 1 1
? 1 2
! 2 1
Ví dụ bổ sung: p=[2,1] có 1 nghịch thế; đổi chỗ hai phần tử được [1,2] với 0 nghịch thế.

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