Submission #855480

#	Time	Username	Problem	Language	Result	Execution time	Memory
855480		tvladm2009	Giraffes (JOI22_giraffes)	C++17	32 / 100	3934 ms	600 KiB

giraffes

#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 <= 13) {
    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;
    };

    int sol = (int) 1e9;
    vector<bool> vis(n + 1, 0);
    vector<int> perm;
    function<void(int)> bkt = [&] (int pos) {
      if (pos == n + 1) {
        if (isgood(perm)) {
          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);
          int mn = perm.back(), mx = perm.back();
          bool ok = true;
          for (int l = pos - 1; l >= 0; l--) {
            mx = max(mx, perm[l]);
            mn = min(mn, perm[l]);
            if (mn != perm[l] && mx != perm[l] && mn != perm.back() && mx != perm.back()) {
              ok = false;
              break;
            }
          }
          if (ok) bkt(pos + 1);
          perm.pop_back();
          vis[i] = 0;
        }
      }
    };
    bkt(1);
    cout << sol << "\n";
    return 0;
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 41