CF--思维练习--CodeForces - 220C Little Elephant and Shifts （STL模拟）

ACM思维题训练集合

The Little Elephant has two permutations a and b of length n, consisting of numbers from 1 to n, inclusive. Let’s denote the i-th (1 ≤ i ≤ n) element of the permutation a as ai, the j-th (1 ≤ j ≤ n) element of the permutation b — as bj.

The distance between permutations a and b is the minimum absolute value of the difference between the positions of the occurrences of some number in a and in b. More formally, it’s such minimum |i - j|, that ai = bj.

A cyclic shift number i (1 ≤ i ≤ n) of permutation b consisting from n elements is a permutation bibi + 1… bnb1b2… bi - 1. Overall a permutation has n cyclic shifts.

The Little Elephant wonders, for all cyclic shifts of permutation b, what is the distance between the cyclic shift and permutation a?

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the size of the permutations. The second line contains permutation a as n distinct numbers from 1 to n, inclusive. The numbers are separated with single spaces. The third line contains permutation b in the same format.

Output

In n lines print n integers — the answers for cyclic shifts. Print the answers to the shifts in the order of the shifts’ numeration in permutation b, that is, first for the 1-st cyclic shift, then for the 2-nd, and so on.

Examples

Input

2

1 2

2 1

Output

1

0

Input

4

2 1 3 4

3 4 2 1

Output

2

1

0

1

这个题预处理一下初始的dis，然后用mutiset模拟即可

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int a[maxn],b[maxn];

multiset<int> ms;

int main()

{

    int n, x;

    scanf("%d", &n);

    for (int i = 0; i < n; ++i)

    {

        scanf("%d", &x);

        a[x] = i;

    }

    for (int i = 0; i < n; ++i)

    {

        scanf("%d", &b[i]);

        ms.insert(i - a[b[i]]);

    }

    for (int i = 0; i < n; ++i)

    {

        auto po = ms.lower_bound(i);

        int ans = 0X3F3F3F3F;

        if (po != ms.end())

            ans = min(ans, *po - i);

        else if (po != ms.begin())

            ans = min(ans, i - *(--po));

        printf("%d\n", ans);

        po = ms.find(i - a[b[i]]);

        ms.erase(po);

        ms.insert(i - a[b[i]] + n);

    }

}

巴特西

CF--思维练习--CodeForces - 220C Little Elephant and Shifts （STL模拟）

最新文章

热门文章