oj.uz

Submission #901031

# Submission time Handle Problem Language Result Execution time Memory
901031 2024-01-09T06:13:07 Z dsyz Pancake (NOI12_pancake) C++17
25 / 25
 146 ms 25920 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 25680 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 25496 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 25684 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 25920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 25696 KB Output is correct