#P16736. 止谎剂

止谎剂

题目描述

给定两个 1,2,…,n1,2,\ldots,n 的排列:

a1,a2,…,ana_1,a_2,\ldots,a_n

和

b1,b2,…,bnb_1,b_2,\ldots,b_n

同时给定两个非负整数 A,BA,B,满足

0≤A,B≤n(n−1)20\le A,B\le \frac{n(n-1)}2

请构造一个 1,2,…,n1,2,\ldots,n 的排列

c1,c2,…,cnc_1,c_2,\ldots,c_n

使得:

  • 序列 ac1,ac2,…,acna_{c_1},a_{c_2},\ldots,a_{c_n} 的逆序对数量恰好为 AA;
  • 序列 bc1,bc2,…,bcnb_{c_1},b_{c_2},\ldots,b_{c_n} 的逆序对数量恰好为 BB。

若不存在满足条件的排列,输出 -1;若存在多组解,输出任意一组即可。

一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n 的逆序对数量,定义为满足

1≤i<j≤n,pi>pj1\le i<j\le n,\qquad p_i>p_j

的有序对 (i,j)(i,j) 的数量。

输入格式

第一行包含三个整数 n,A,Bn,A,B。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

保证 aa 和 bb 都是 1,2,…,n1,2,\ldots,n 的排列。

输出格式

若无解,输出一行一个整数:

-1

否则,输出一行 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n,表示你构造的排列。相邻整数之间用空格分隔。

本题使用 Special Judge。只要输出满足题意的任意一种合法构造即可。

样例 1

4 1 2
3 1 4 2
2 4 3 1
4 2 1 3

样例 1 解释

对于输出的排列 c=(4,2,1,3)c=(4,2,1,3):

$$(a_{c_1},a_{c_2},a_{c_3},a_{c_4})=(a_4,a_2,a_1,a_3)=(2,1,3,4)$$

其逆序对数量为 11。

同时:

$$(b_{c_1},b_{c_2},b_{c_3},b_{c_4})=(b_4,b_2,b_1,b_3)=(1,4,2,3)$$

其逆序对数量为 22。

样例 2

4 1 0
3 1 4 2
2 4 3 1
-1

数据范围

对于全部数据:

1≤n≤2000001\le n\le 200000 0≤A,B≤n(n−1)20\le A,B\le \frac{n(n-1)}2

保证输入的 aa 和 bb 均为 1,2,…,n1,2,\ldots,n 的排列。