Submission #654966

#	Time	Username	Problem	Language	Result	Execution time	Memory
654966		ShirAriel	Pancake (NOI12_pancake)	C++17	25 / 25	231 ms	6092 KiB

pancake

#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;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 8 / 8
• Subtask 5: 5 / 5