This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (n <= 7) {
int sol = (int) 1e9;
vector<bool> vis(n + 1, 0);
vector<int> perm;
function<void(int)> bkt = [&] (int pos) {
if (pos == n + 1) {
bool ok = true;
for (int l = 0; l < n; l++) {
int mn = n + 1, mx = 0;
for (int r = l; r < n; r++) {
mx = max(mx, perm[r]);
mn = min(mn, perm[r]);
if (mn != perm[l] && mn != perm[r] && mx != perm[l] && mx != perm[r]) {
ok = false;
}
}
}
if (ok) {
int cost = 0;
for (int i = 0; i < n; i++) {
cost += (perm[i] != a[i]);
}
sol = min(sol, cost);
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = 1;
perm.push_back(i);
bkt(pos + 1);
perm.pop_back();
vis[i] = 0;
}
}
};
bkt(1);
cout << sol << "\n";
return 0;
}
/// ** \/ sau /\ **
int sol = (int) 1e9;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> down, up;
vector<int> cnt(n + 1, 0);
for (int b = 0; b < n; b++) {
if (mask & (1 << b)) {
down.push_back(a[b]);
cnt[a[b]]++;
}
}
sort(down.rbegin(), down.rend());
for (int b = 1; b <= n; b++) {
if (cnt[b] == 0) {
up.push_back(b);
}
}
if (down.empty() || up.empty() || down.back() < up[0]) {
vector<int> v;
for (auto &x : down) {
v.push_back(x);
}
for (auto &x : up) {
v.push_back(x);
}
assert((int) v.size() == n);
int cost = 0;
for (int i = 0; i < n; i++) {
cost += (v[i] != a[i]);
}
sol = min(sol, cost);
}
if (down.empty() || up.empty() || up.back() > down[0]) {
vector<int> v;
for (auto &x : up) {
v.push_back(x);
}
for (auto &x : down) {
v.push_back(x);
}
assert((int) v.size() == n);
int cost = 0;
for (int i = 0; i < n; i++) {
cost += (v[i] != a[i]);
}
sol = min(sol, cost);
}
}
cout << sol << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |