#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef int ll;
const int MAX_N = 8;
ll getval(ll val, vector<ll>& zip)
{
ll l = 0, r = zip.size() - 1, mid;
while (l <= r)
{
mid = (l + r) / 2;
if (zip[mid] == val) return mid;
if (zip[mid] < val)
l = mid + 1;
else
r = mid - 1;
}
return -1;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
map<vector<ll>, ll> ans;
vector<ll> curr(MAX_N);
for (ll i = 0; i < MAX_N; i++)
curr[i] = i;
queue<vector<ll>> q;
q.push(curr);
ans[curr] = 0;
while (!q.empty())
{
curr = q.front();
q.pop();
for (ll i = 2; i <= MAX_N; i++)
{
vector<ll> rev = curr;
reverse(rev.begin(), rev.begin() + i);
if (ans.find(rev) == ans.end() || ans[rev] > ans[curr] + 1)
{
ans[rev] = ans[curr] + 1;
q.push(rev);
}
}
}
ll t;
cin >> t;
for (ll i = 0; i < t; i++)
{
ll n;
cin >> n;
vector<ll> query(n);
for (ll j = 0; j < n; j++)
cin >> query[j];
reverse(query.begin(), query.end());
vector<ll> zip;
for (ll j = 0; j < n; j++)
zip.push_back(query[j]);
sort(zip.begin(), zip.end());
zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
for (ll j = 0; j < n; j++)
query[j] = getval(query[j], zip);
for (ll j = query.size(); j < MAX_N; j++)
query.push_back(j);
cout << ans[query] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
6092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
5980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
5896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
5980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
6060 KB |
Output is correct |
