Các Pharaoh sử dụng chuyển động tương đối và lực hấp dẫn của các hành tinh để tăng tốc phi thuyền. Giả sử một phi thuyền lần lượt đi qua \(n\) hành tinh có tốc độ quỹ đạo \(p[0],p[1],\ldots,p[n-1]\). Với mỗi hành tinh, các nhà khoa học của Pharaoh có thể chọn dùng hành tinh đó để tăng tốc phi thuyền hoặc không. Để tiết kiệm năng lượng, sau khi tăng tốc bằng một hành tinh có tốc độ quỹ đạo \(p[i]\), phi thuyền không thể tiếp tục được tăng tốc bằng bất kỳ hành tinh nào có tốc độ quỹ đạo \(p[j]<p[i]\).

Nói cách khác, các hành tinh được chọn tạo thành một dãy con tăng dần của \(p[0],p[1],\ldots,p[n-1]\). Một dãy con của \(p\) là một dãy thu được bằng cách xóa đi không, một hoặc nhiều phần tử của \(p\) mà không thay đổi thứ tự các phần tử còn lại. Chẳng hạn, \([0]\), \([]\), \([0,2]\) và \([0,1,2]\) là các dãy con của \([0,1,2]\), còn \([2,1]\) thì không.

Các nhà khoa học xác định rằng có tổng cộng \(k\) cách khác nhau để chọn một nhóm hành tinh nhằm tăng tốc phi thuyền, nhưng họ đã làm mất toàn bộ dữ liệu về tốc độ quỹ đạo, kể cả giá trị \(n\). Tuy nhiên, họ nhớ rằng \((p[0],p[1],\ldots,p[n-1])\) là một hoán vị của \(0,1,\ldots,n-1\). Một hoán vị là một dãy chứa mỗi số nguyên từ \(0\) đến \(n-1\) đúng một lần. Hãy tìm một hoán vị \(p[0],p[1],\ldots,p[n-1]\) có thể xảy ra và có độ dài đủ nhỏ.

Bạn cần giải bài toán cho \(q\) phi thuyền khác nhau. Với phi thuyền thứ \(i\), bạn nhận được số nguyên \(k_i\), là số cách khác nhau để chọn một nhóm hành tinh tăng tốc phi thuyền. Hãy tìm một dãy tốc độ quỹ đạo có độ dài \(n_i\) đủ nhỏ sao cho có đúng \(k_i\) cách chọn một dãy con các hành tinh với tốc độ quỹ đạo tăng dần.

Lưu ý rằng dãy con rỗng cũng được tính là một dãy con tăng dần.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau. Chữ ký C++ trong tệp tiêu đề chính thức là:

std::vector<int> construct_permutation(long long k);

• k: số dãy con tăng dần mong muốn.
• Hàm phải trả về một mảng gồm \(n\) phần tử, mỗi phần tử nằm trong đoạn từ \(0\) đến \(n-1\).
• Mảng trả về phải là một hoán vị hợp lệ có đúng \(k\) dãy con tăng dần.
• Hàm được gọi tổng cộng \(q\) lần. Mỗi lần gọi phải được xử lý như một trường hợp độc lập.

Ràng buộc

• \(1\le q\le100\).
• \(2\le k_i\le10^{18}\) với mọi \(0\le i\le q-1\).

Phân nhóm và cách tính điểm

1. (\(10\) điểm) \(2\le k_i\le90\) với mọi \(0\le i\le q-1\). Nếu tất cả các hoán vị bạn trả về đều đúng và có độ dài không quá \(90\), bạn nhận được \(10\) điểm; nếu không, bạn nhận được \(0\) điểm cho phân nhóm này.

2. (\(90\) điểm) Không có ràng buộc bổ sung. Gọi \(m\) là độ dài lớn nhất trong tất cả các hoán vị bạn trả về. Điểm của phân nhóm này được tính như sau:

   Điều kiện	Điểm
   \(m\le90\)	\(90\)
   \(90<m\le120\)	\(90-\dfrac{m-90}{3}\)
   \(120<m\le5000\)	\(80-\dfrac{m-120}{65}\)
   \(m>5000\)	\(0\)

Ví dụ

construct_permutation(3);

construct_permutation(8);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau; đây chỉ là giao diện của trình chấm mẫu, không phải giao diện chuẩn vào/ra của bài:

• Dòng \(1\): \(q\).
• Dòng \(2+i\) (\(0\le i\le q-1\)): \(k_i\).

Với mỗi \(k_i\), trình chấm mẫu in trên một dòng giá trị mà construct_permutation trả về, hoặc một thông báo lỗi nếu xảy ra lỗi.

Tệp ví dụ chính thức dành cho trình chấm mẫu là:

2
3
8

2
1 0
3
0 1 2

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2022, Ai Cập: gói nguồn chính thức của bài Permutation.