Submission #901031

#	Time	Username	Problem	Language	Result	Execution time	Memory
901031		dsyz	Pancake (NOI12_pancake)	C++17	25 / 25	146 ms	25920 KiB

pancake

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (50000)
vector<ll> v[9][MAXN];
ll dist[9][MAXN];
bool visited[9][MAXN];
map<vector<ll>,ll> ind[9];
queue<ll> q;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	for(ll N = 1;N <= 8;N++){
		vector<ll> pancakes;
		for(ll i = 0;i < N;i++){
			pancakes.push_back(i);
		}
		ll cnt = 1;
		do{
			ind[N][pancakes] = cnt;
			for(ll j = N - 2;j >= 0;j--){
				reverse(pancakes.begin() + j,pancakes.end());
				if(ind[N][pancakes]){
					v[N][cnt].push_back(ind[N][pancakes]);
					v[N][ind[N][pancakes]].push_back(cnt);
				}
				reverse(pancakes.begin() + j,pancakes.end());
			}
			cnt++;
		}while(next_permutation(pancakes.begin(),pancakes.end()));
		ll finalind = cnt - 1;
		q.push(finalind);
		dist[N][finalind] = 0;
		visited[N][finalind] = 1;
		while(!q.empty()){
			ll x = q.front();
			q.pop();
			visited[N][x] = 1;
			for(auto u : v[N][x]){
				if(!visited[N][u]){
					q.push(u);
					dist[N][u] = dist[N][x] + 1;
					visited[N][u] = 1;
				}
			}
		}
	}
	ll t;
	cin>>t;
	while(t--){
		ll N;
		cin>>N;
		vector<ll> pancakes, d;
		for(ll i = 0;i < N;i++){
			ll a;
			cin>>a;
			pancakes.push_back(a);
			d.push_back(a);
		}
		sort(d.begin(),d.end());
		d.resize(unique(d.begin(),d.end()) - d.begin());
		for(ll i = 0;i < N;i++){
			pancakes[i] = lower_bound(d.begin(),d.end(),pancakes[i]) - d.begin();
		}
		cout<<dist[N][ind[N][pancakes]]<<'\n';
	}
}

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