trang chủ / đề bài / buildperm

Xây dựng hoán vị

Đề bài

Mô tả

Cho ba số nguyên n, a, b. Hãy xác định xem có tồn tại một hoán vị p1,p2,…,pn của các số nguyên từ 1 đến n thỏa mãn đồng thời hai điều kiện sau hay không:

  • Có đúng a chỉ số i với 2≤i≤n−1 sao cho pi−1<pi>pi+1 (nói cách khác, có đúng a cực đại địa phương).
  • Có đúng b chỉ số i với 2≤i≤n−1 sao cho pi−1>pi<pi+1 (nói cách khác, có đúng b cực tiểu địa phương).

Lưu ý rằng hai vị trí đầu mút i=1 và i=n không bao giờ được tính là cực trị địa phương.

Nếu tồn tại hoán vị như vậy, hãy in ra một hoán vị bất kỳ thỏa mãn.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên t (1≤t≤104) là số lượng bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm một dòng chứa ba số nguyên n, a, b (2≤n≤105, 0≤a,b≤n).

Tổng n trên tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu:

  • Nếu không tồn tại hoán vị thỏa mãn, in ra −1.
  • Ngược lại, in ra n số nguyên là một hoán vị thỏa mãn. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤t≤104
  • 2≤n≤105
  • 0≤a,b≤n
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 105

Ví dụ

Input Output Giải thích
3
4 1 1
6 1 2
6 4 0
1 4 2 3
6 1 5 2 3 4
-1
Bộ 1: với hoán vị [1,4,2,3] ta có p1<p2>p3 nên i=2 là cực đại, và p2>p3<p4 nên i=3 là cực tiểu; đúng a=1, b=1.
Bộ 2: [6,1,5,2,3,4] có cực đại tại i=3, cực tiểu tại i=2 và i=4.
Bộ 3: cần 4 cực đại nhưng 0 cực tiểu, không thể vì hai loại cực trị luôn xen kẽ nhau.
4
2 0 0
3 1 0
5 1 1
5 3 0
1 2
1 3 2
1 5 2 3 4
-1
Bộ 1: n=2 không có vị trí trong nên bắt buộc a=b=0.
Bộ 2: [1,3,2] có duy nhất cực đại tại i=2.
Bộ 3: [1,5,2,3,4] có cực đại tại i=2, cực tiểu tại i=3.
Bộ 4: |a−b|=3>1 nên vô nghiệm.

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