CodeForces 220C. Little Elephant and Shifts

//By momo
#include<set>
#include<cstdio>
#include<algorithm>
#define N 100010
using namespace std;
multiset<int> s;
int n, a[N], b[N], c[N], i, j;
int main(){
    scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d", &j), c[j] = i;
    for(i = 0; i < n; i++) scanf("%d", &b[i]), s.insert(i - c[b[i]]);
    for(i = 0; i < n; i++){
        multiset<int>::iterator it = s.lower_bound(i);
        int ans = 999999999;
        if(it != s.end())   ans = min(ans, *it-i);
        if(it != s.begin()) ans = min(ans, i-(*(--it)));
        printf("%d\n", ans);
        s.erase(s.find(i-c[b[i]]));
        s.insert((i+n)-c[b[i]]);
    }
}

There are so much great problems in Codeforces.

This is one of the best problem I have.

It's not hard but fun, and I've learned a lot from it.

Multiset:

1. insert(x): log(Size)

   insert(pos, x): if x is inserted right after pos, Constant.

   insert(begin, end): Nlog(N+size)

2. erase(pos): Constant

   erase(x): Erase all value of x

3. lower_bound(x): find the pos with value >= x

   upper_bound(x):                         >

4. equal_range(x): return a pair of iterator

5. find(x): return iterator point at x(if not found return end())

Multiset is a pretty useful tool, it's an upgrade of set, with all of the functions from set available in it.