Language: C++

//
//  main.cpp
//  AOJ
//
//  Created by user on 2014/06/01.
//  Copyright (c) 2014年 user. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;

const int SIZE = 3628810;
typedef pair< vector<int>, int > Pack;

int getPermId(const vector<int>& v){
    const int N = (int)v.size();
    
    int fact = 1;
    int res = 0;
    
    for(int i=N-1;i>=0;i--){
        for(int j=i+1;j<N;j++){
            if(v[j] < v[i]){
                res += fact;
            }
        }
        fact *= (N - i);
    }
    
    return res;
}

int dist[2][SIZE];
vector<Pack> Queue[2];

int bfs(const vector<int>& start, const vector<int>& goal){
    memset(dist, -1, sizeof(dist));
    
    const int N = (int)start.size();
    const int startId = getPermId(start);
    const int goalId  = getPermId(goal);
    
    if(startId == goalId){
        return 0;
    }
    
    int curr = 0, next = 1;
    
    dist[curr][startId] = 0;
    dist[next][goalId]  = 0;
    
    Queue[curr].push_back(make_pair(start, startId));
    Queue[next].push_back(make_pair(goal,  goalId));
    
    for(;;){
        vector<Pack> nextQueue;
        for(int i=0;i<Queue[curr].size();i++){
            const Pack &pack = Queue[curr][i];
            
            const vector<int> &perm = pack.first;
            int permId = pack.second;
            int nowCost = dist[curr][permId];
            
            for(int s=0;s<N;s++)for(int t=s+1;t<N;t++){
                reverse(perm.begin() + s, perm.begin() + t + 1);
            
                int nextPermId = getPermId(perm);
                if(dist[curr][nextPermId] == -1){
                    dist[curr][nextPermId] = nowCost + 1;
                
                    if(dist[next][nextPermId] != -1){
                        return dist[curr][nextPermId] + dist[next][nextPermId];
                    } else {
                        nextQueue.push_back(make_pair(perm, nextPermId));
                    }
                }
                
                reverse(perm.begin() + s, perm.begin() + t + 1);
            }
        }
        Queue[curr].swap(nextQueue);
        
        swap(curr, next);
    }
    
    return 1;
}

int main(){
    int N;
    cin >> N;
    
    vector<int> start(N);
    for(int i=0;i<N;i++){
        cin >> start[i];
        --start[i];
    }
    
    vector<int> goal = start;
    sort(goal.begin(), goal.end());
    
    int res = bfs(start, goal);
    cout << res << endl;
    
    return 0;
}

Compiler output:
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:9:
/usr/include/c++/14/bits/stl_algobase.h: In instantiation of 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator2 = __gnu_cxx::__normal_iterator<const int*, vector<int> >]':
/usr/include/c++/14/bits/stl_algo.h:1062:18:   required from 'void std::__reverse(_RandomAccessIterator, _RandomAccessIterator, random_access_iterator_tag) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1062 |           std::iter_swap(__first, __last);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1089:21:   required from 'void std::reverse(_BIter, _BIter) [with _BIter = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1089 |       std::__reverse(__first, __last, std::__iterator_category(__first));
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:70:24:   required from here
   70 |                 reverse(perm.begin() + s, perm.begin() + t + 1);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:185:11: error: no matching function for call to 'swap(const int&, const int&)'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41:
/usr/include/c++/14/bits/exception_ptr.h:229:5: note: candidate: 'void std::__exception_ptr::swap(exception_ptr&, exception_ptr&)'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
/usr/include/c++/14/bits/exception_ptr.h:229:25: note:   no known conversion for argument 1 from 'const int' to 'std::__exception_ptr::exception_ptr&'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |          ~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/bits/exception_ptr.h:41:
/usr/include/c++/14/bits/move.h:226:5: note: candidate: 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&)'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/move.h:226:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/14/bits/move.h:37:
/usr/include/c++/14/type_traits: In substitution of 'template<bool _Cond, class _Tp> using std::__enable_if_t = typename std::enable_if::type [with bool _Cond = false; _Tp = void]':
/usr/include/c++/14/type_traits:2323:11:   required by substitution of 'template<class ... _Cond> using std::_Require = std::__enable_if_t<((bool)std::__and_<_Bn>::value)> [with _Cond = {std::__not_<std::__is_tuple_like<const int> >, std::is_move_constructible<const int>, std::is_move_assignable<const int>}]'
 2323 |     using _Require = __enable_if_t<__and_<_Cond...>::value>;
      |           ^~~~~~~~
/usr/include/c++/14/bits/move.h:226:5:   required by substitution of 'template<class _Tp> std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&) [with _Tp = const int]'
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/stl_algobase.h:185:11:   required from 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator2 = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1062:18:   required from 'void std::__reverse(_RandomAccessIterator, _RandomAccessIterator, random_access_iterator_tag) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1062 |           std::iter_swap(__first, __last);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1089:21:   required from 'void std::reverse(_BIter, _BIter) [with _BIter = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1089 |       std::__reverse(__first, __last, std::__iterator_category(__first));
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:70:24:   required from here
   70 |                 reverse(perm.begin() + s, perm.begin() + t + 1);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/type_traits:138:11: error: no type named 'type' in 'struct std::enable_if<false, void>'
  138 |     using __enable_if_t = typename enable_if<_Cond, _Tp>::type;
      |           ^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h: In instantiation of 'void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = __gnu_cxx::__normal_iterator<const int*, vector<int> >; _ForwardIterator2 = __gnu_cxx::__normal_iterator<const int*, vector<int> >]':
/usr/include/c++/14/bits/stl_algo.h:1062:18:   required from 'void std::__reverse(_RandomAccessIterator, _RandomAccessIterator, random_access_iterator_tag) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1062 |           std::iter_swap(__first, __last);
      |           ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1089:21:   required from 'void std::reverse(_BIter, _BIter) [with _BIter = __gnu_cxx::__normal_iterator<const int*, vector<int> >]'
 1089 |       std::__reverse(__first, __last, std::__iterator_category(__first));
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:70:24:   required from here
   70 |                 reverse(perm.begin() + s, perm.begin() + t + 1);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/move.h:250:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> std::__enable_if_t<((bool)std::__is_swappable<_Tp>::value)> std::swap(_Tp (&)[_Nm], _Tp (&)[_Nm])'
  250 |     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
      |     ^~~~
/usr/include/c++/14/bits/move.h:250:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algobase.h:185:11: note:   mismatched types '_Tp [_Nm]' and 'const int'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/bits/stl_pair.h:1089:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)'
 1089 |     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1089:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algobase.h:185:11: note:   mismatched types 'std::pair<_T1, _T2>' and 'const int'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)' (deleted)
 1106 |     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algobase.h:185:11: note:   mismatched types 'std::pair<_T1, _T2>' and 'const int'
  185 |       swap(*__a, *__b);
      |       ~~~~^~~~~~~~~~~~