trang chủ / đề bài / icpc23_mb_h

Nghịch thế

Đề bài

Mô tả

Một hoán vị độ dài N là một mảng chứa mỗi số nguyên từ 1 đến N đúng một lần. Một nghịch thế của hoán vị P là một cặp vị trí (i,j) sao cho i<j và Pi>Pj.

Cho ba số nguyên N, M và K. Hãy in ra hoán vị độ dài N có đúng M nghịch thế và đứng thứ K theo thứ tự từ điển (tính từ nhỏ đến lớn) trong số các hoán vị như vậy. Nếu không có hoán vị như vậy, in ra −1.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên N, M và K (1≤N≤100, 0≤M≤N(N−1)2, 1≤K≤1018).

Dữ liệu ra

In ra một dòng gồm N số nguyên là hoán vị cần tìm. Nếu không có hoán vị như vậy, in ra −1.

Ràng buộc

  • 1≤N≤100
  • 0≤M≤N(N−1)2
  • 1≤K≤1018

Ví dụ

Input Output Giải thích
5 1 2 1 2 4 3 5 Các hoán vị độ dài 5 có đúng 1 nghịch thế theo thứ tự từ điển là 1 2 3 5 4, 1 2 4 3 5, 1 3 2 4 5, 2 1 3 4 5; hoán vị thứ 2 là 1 2 4 3 5.
5 0 2 -1 Chỉ có một hoán vị không có nghịch thế (1 2 3 4 5).

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