Submission #1219250

#TimeUsernameProblemLanguageResultExecution timeMemory
1219250trimkusGroup Photo (JOI21_ho_t3)C++20
5 / 100
5094 ms468 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int calc(int n, vector<int>& a, vector<int> b) {
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int id = -1;
		for (int j = i; j < n; ++j) {
			if (b[j] == a[i]) {
				id = j;
				break;
			}
		}
		while (id > i) {
			swap(b[id - 1], b[id]);
			id -= 1;
			res += 1;
		}
	}
	assert(b == a);
	return res;
}


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	iota(begin(a), end(a), 1);
	vector<int> b(n);
	for (auto& u : b) cin >> u;
	int res = n * n;
	do {
		int mx = 0;
		bool ok = true;
		for (int i = 0; i < n; ++i) {
			if (2 * i + a[i] <= mx) {
				ok = false;
				break;
			}
			mx = max(mx, 2 * i + a[i]);
		}
		if (ok) {
			res = min(res, calc(n, b, a));
			//~ cout << calc(n, a, b) << " = ";
			//~ for (auto& u : a) {
				//~ cout << u << " ";
			//~ }
			//~ cout << "\n";
		}
	} while (next_permutation(begin(a), end(a)));
	cout << res << "\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...