trang chủ / đề bài / icpc22_nat_i

Nghịch thế

Đề bài

Mô tả

Hoán vị là một chủ đề quan trọng và thú vị trong toán học. Một trong những khái niệm nổi tiếng nhất liên quan đến hoán vị là nghịch thế.

Nhắc lại, dãy số nguyên p1,p2,…,pn được gọi là một hoán vị của các số nguyên 1,2,…,n khi và chỉ khi:

  • Với mọi 1≤i≤n, 1≤pi≤n.
  • Với mọi 1≤i<j≤n, pi≠pj.

Một nghịch thế của hoán vị p1,p2,…,pn là một cặp (i,j) sao cho i<j và pi>pj.

Trong bài toán này, có một hoán vị bí mật p1,p2,…,pn của các số nguyên 1,2,…,n. Bạn được cho một mảng hai chiều c, trong đó cu,v bằng số nghịch thế của p nếu ta đổi chỗ pu và pv. Nhiệm vụ của bạn là tìm hoán vị bí mật này.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤1000), độ dài của hoán vị.
  • Dòng thứ u trong n dòng tiếp theo chứa n số nguyên cu,1,cu,2,…,cu,n (0≤cu,v≤n(n−1)2).

Dữ liệu vào đảm bảo có ít nhất một hoán vị bí mật hợp lệ.

Dữ liệu ra

In ra một dòng gồm n số nguyên p1,p2,…,pn là hoán vị bí mật. Nếu có nhiều hoán vị thỏa mãn, in ra một hoán vị bất kỳ.

Ràng buộc

  • 1≤n≤1000.
  • 0≤cu,v≤n(n−1)2.

Ví dụ

Input Output Giải thích
2
0 1
1 0
1 2 Hoán vị (1,2) không có nghịch thế; đổi chỗ hai phần tử được (2,1) có 1 nghịch thế.
3
2 3 1
3 2 1
1 1 2
2 3 1 Hoán vị (2,3,1) có 2 nghịch thế. Ví dụ, đổi chỗ p1 và p2 được (3,2,1) có 3 nghịch thế, nên c1,2=3.

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