Submission #942133

#TimeUsernameProblemLanguageResultExecution timeMemory
942133dsyzGroup Photo (JOI21_ho_t3)C++17
5 / 100
5031 ms460 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll H[N], arr[N];
	for(ll i = 0;i < N;i++){
		cin>>H[i];
		arr[i] = H[i];
	}
	sort(arr,arr + N);
	ll ans = 1e18;
	do{
		bool ok = 1;
		for(ll i = 1;i < N;i++){
			if(arr[i - 1] >= arr[i] + 2){
				ok = 0;
			}
		}
		if(!ok) continue;
		ll sum = 0;
		ll tmp[N];
		for(ll i = 0;i < N;i++){
			tmp[i] = H[i];
		}
		for(ll i = 0;i < N;i++){
			ll pos = 0;
			for(ll j = 0;j < N;j++){
				if(tmp[j] == arr[i]){
					pos = j;
				}
			}
			while(pos > i){
				swap(tmp[pos - 1],tmp[pos]);
				pos--;
				sum++;
			}
			while(pos < i){
				swap(tmp[pos],tmp[pos + 1]);
				pos++;
				sum++;
			}
		}
		ans = min(ans,sum);
	}while(next_permutation(arr,arr + N));
	cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...