oj.uz

Submission #654492

# Submission time Handle Problem Language Result Execution time Memory
654492 2022-10-31T13:42:40 Z Carmel_Ab1 Pancake (NOI12_pancake) C++17
25 / 25
 334 ms 7656 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;

typedef long long 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";
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 7480 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 7388 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 7472 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 7656 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 7480 KB Output is correct