解法
最初に転倒数を求めて、それの1/2だけ転倒するようにバブルソートする。バブルソートに一部は Binary Indexed Tree を使うと高速化できる。
コード
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public void solve() {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt() - 1;
}
int[] b = new int[n];
for (int i = 0; i < n; i++) {
b[i] = scanner.nextInt() - 1;
}
scanner.close();
int[] ia = new int[n];
for (int i = 0; i < n; i++) {
ia[a[i]] = i;
}
int[] iab = new int[n];
for (int i = 0; i < n; i++) {
iab[i] = ia[b[i]];
}
long inverse = 0;
FenwickTree fenwickTree = new FenwickTree(n);
for (int i = 0; i < n; i++) {
inverse += i - fenwickTree.sum(iab[i]);
fenwickTree.add(iab[i], 1);
}
if (inverse % 2 == 1) {
System.out.println(-1);
return;
}
FenwickTree bubbleTree = new FenwickTree(n);
int[] where = new int[n];
for (int i = 0; i < n; i++) {
where[iab[i]] = i;
}
inverse /= 2;
for (int i = 0; i < n; i++) {
int bubbleSort = where[i] - bubbleTree.sum(where[i]);
bubbleTree.add(where[i], 1);
if (inverse < bubbleSort) {
int[] halfSorted = new int[n];
for (int j = 0; j < i; j++) {
halfSorted[j] = j;
}
int over = (int) (bubbleSort - inverse);
int cur = i;
for (int j = 0; j < n; j++) {
if (iab[j] > i) {
if (over == 0) {
halfSorted[cur] = i;
cur++;
}
over--;
halfSorted[cur] = iab[j];
cur++;
}
}
StringBuilder builder = new StringBuilder();
for (int j = 0; j < n; j++) {
if (j > 0) {
builder.append(" ");
}
builder.append(a[halfSorted[j]] + 1);
}
System.out.println(builder.toString());
return;
}
inverse -= bubbleSort;
}
StringBuilder builder = new StringBuilder();
for (int j = 0; j < n; j++) {
if (j > 0) {
builder.append(" ");
}
builder.append(a[j] + 1);
}
System.out.println(builder.toString());
}
public static void main(String[] args) {
new Main().solve();
}
}
class FenwickTree {
int[] tree;
public FenwickTree(int N) {
tree = new int[N + 2];
}
public int sum(int index) {
int sum = 0;
for (index++; index > 0; index -= index & -index) {
sum += tree[index];
}
return sum;
}
public void add(int index, int value) {
if (value == 0 || index < 0) {
return;
}
int n = tree.length;
for (index++; index < n; index += index & -index)
tree[index] += value;
}
public int findGFenwick(int v) {
int i = 0;
int n = tree.length;
for (int b = Integer.highestOneBit(n); b != 0 && i < n; b >>= 1) {
if (i + b < n) {
int t = i + b;
if (v >= tree[t]) {
i = t;
v -= tree[t];
}
}
}
return v != 0 ? -(i + 1) : i - 1;
}
public int valFenwick(int i) {
return sum(i) - sum(i - 1);
}
public int[] restoreFenwick(int[] ft) {
int n = ft.length - 1;
int[] ret = new int[n];
for (int i = 0; i < n; i++)
ret[i] = sum(i);
for (int i = n - 1; i >= 1; i--)
ret[i] -= ret[i - 1];
return ret;
}
public int before(int x) {
int u = sum(x - 1);
if (u == 0)
return -1;
return findGFenwick(u - 1) + 1;
}
public int after(int x) {
int u = sum(x);
int f = findGFenwick(u);
if (f + 1 >= tree.length - 1)
return -1;
return f + 1;
}
public int[] buildFenwick(int[] a) {
int n = a.length;
int[] ft = new int[n + 1];
System.arraycopy(a, 0, ft, 1, n);
for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
for (int i = k; i <= n; i += k) {
ft[i] += ft[i - h];
}
}
return ft;
}
public int[] buildFenwick(int n, int v) {
int[] ft = new int[n + 1];
Arrays.fill(ft, 1, n + 1, v);
for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
for (int i = k; i <= n; i += k) {
ft[i] += ft[i - h];
}
}
return ft;
}
}