Submission #942133

#	Time	Username	Problem	Language	Result	Execution time	Memory
942133		dsyz	Group Photo (JOI21_ho_t3)	C++17	5 / 100	5031 ms	460 KiB

Main

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36