oj.uz

Submission #855478

# Submission time Handle Problem Language Result Execution time Memory
855478 2023-10-01T09:55:52 Z tvladm2009 Giraffes (JOI22_giraffes) C++17
10 / 100
 1 ms 348 KB 
#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);
    }
  }

  /// **// sau \\**

  function<bool(vector<int>)> isgood = [&](vector<int> perm) {
    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;
        }
      }
    }
    return ok;
  };

  for (int mask = 0; mask < (1 << n); mask++) {
    vector<int> x, y;
    for (int b = 0; b < n; b++) {
      if (mask & (1 << b)) {
        x.push_back(a[b]);
      } else {
        y.push_back(a[b]);
      }
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    vector<int> v;
    for (auto &it : x) {
      v.push_back(it);
    }
    for (auto &it : y) {
      v.push_back(it);
    }
    if (isgood(v)) {
      int cost = 0;
      for (int i = 0; i < n; i++) {
        cost += (v[i] != a[i]);
      }
      sol = min(sol, cost);
    }
    sort(x.rbegin(), x.rend());
    sort(y.rbegin(), y.rend());
    v.clear();
    for (auto &it : x) {
      v.push_back(it);
    }
    for (auto &it : y) {
      v.push_back(it);
    }
    if (isgood(v)) {
      int cost = 0;
      for (int i = 0; i < n; i++) {
        cost += (v[i] != a[i]);
      }
      sol = min(sol, cost);
    }
  }
  cout << sol << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -