답안 #855480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855480	2023-10-01T10:02:13 Z	tvladm2009	Giraffes (JOI22_giraffes)	C++17	32 / 100	3934 ms	600 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	380 KB	Output is correct
5	Correct	0 ms	348 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

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	380 KB	Output is correct
5	Correct	0 ms	348 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	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	452 KB	Output is correct
13	Correct	40 ms	600 KB	Output is correct
14	Correct	183 ms	428 KB	Output is correct
15	Correct	847 ms	432 KB	Output is correct
16	Correct	840 ms	428 KB	Output is correct
17	Correct	3934 ms	436 KB	Output is correct
18	Correct	3911 ms	436 KB	Output is correct
19	Correct	3915 ms	432 KB	Output is correct
20	Correct	3906 ms	436 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	380 KB	Output is correct
5	Correct	0 ms	348 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	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	452 KB	Output is correct
13	Correct	40 ms	600 KB	Output is correct
14	Correct	183 ms	428 KB	Output is correct
15	Correct	847 ms	432 KB	Output is correct
16	Correct	840 ms	428 KB	Output is correct
17	Correct	3934 ms	436 KB	Output is correct
18	Correct	3911 ms	436 KB	Output is correct
19	Correct	3915 ms	432 KB	Output is correct
20	Correct	3906 ms	436 KB	Output is correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	380 KB	Output is correct
5	Correct	0 ms	348 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	Correct	3 ms	348 KB	Output is correct
12	Correct	9 ms	452 KB	Output is correct
13	Correct	40 ms	600 KB	Output is correct
14	Correct	183 ms	428 KB	Output is correct
15	Correct	847 ms	432 KB	Output is correct
16	Correct	840 ms	428 KB	Output is correct
17	Correct	3934 ms	436 KB	Output is correct
18	Correct	3911 ms	436 KB	Output is correct
19	Correct	3915 ms	432 KB	Output is correct
20	Correct	3906 ms	436 KB	Output is correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Halted	0 ms	0 KB	-