Intermediate.
Put your skills to the test.

Problem summary

Rabbit k travels from its cage position to feeder k’s position. Given the two permutations, find the greatest absolute position difference.

Constraints

2 ≤ N ≤ 100000; both rows are permutations of 1…N.

Worked example

Input and output for the worked example discussed below.

5
2 1 5 4 3
3 5 2 4 1

4

Solution analysis

1. Invert the rabbit permutation: position[k] is the cage containing rabbit k. This avoids repeated linear searches for matching labels.
2. Read feeders left to right. A feeder labeled k at position j gives distance |position[k]−j|; keep the largest such distance.
3. In the sample rabbit 3 occupies cage 5 but its feeder is at position 1, giving 4. Rabbit 4 has distance 0. The maximum over all labels is therefore 4.

Why it works

The inverse array locates each rabbit exactly, and each feeder matches the same label. Every computed difference is its prescribed trip, so their maximum is the answer.

Watch out. Match labels, not values at corresponding row indices. Use the same indexing convention for both permutations.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int count;
    cin>>count;
    vector<int>position(count+1);
    for(int cage=1;cage<=count;cage++){
        int rabbit;
        cin>>rabbit;
        position[rabbit]=cage;
    }
    int answer=0;
    for(int feeder=1;feeder<=count;feeder++){
        int label;
        cin>>label;
        // Equal labels identify the matching cage and feeder.
        answer=max(answer,abs(position[label]-feeder));
    }
    cout<<answer<<'\n';
}