oj.uz

Submission #782292

# Submission time Handle Problem Language Result Execution time Memory
782292 2023-07-13T19:02:01 Z ikaurov Ancient Books (IOI17_books) C++14
12 / 100
 6 ms 8532 KB 
// #include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int INF = 1e9;

long long minimum_walk(std::vector<int> p, int s) {
	int n = sz(p);
  ll ans = 0;
  for (int i = 0; i < n; i++){
    ans += abs(i - p[i]);
  }
  int mincycle = -1, maxcycle = -1;
  for (int i = 0; i < n; i++) if (i != p[i]){
    mincycle = i;
    break;
  }
  for (int i = n - 1; i >= 0; i--) if (i != p[i]){
    maxcycle = i;
    break;
  }
  if (mincycle == -1) return 0;
  for (int i = mincycle, mx = -1; i < n;){
    mx = max(mx, p[i]);
    if (mx <= i){
      int j = i + 1;
      while (j < n && j == p[j]) j++;
      if (j == n) break;
      ans += 2 * (j - i), i = j;
    }
    else i++;
  }
  if (s < mincycle) return ans + 2 * (mincycle - s);
  if (s > maxcycle) return ans + 2 * (s - maxcycle);
  vector<bool> cycleend(n);
  for (int i = 0, mx = -1; i < n; i++){
    mx = max(mx, p[i]);
    if (mx <= i) cycleend[i] = 1;
  }

  vector<int> cur, used(n), cid(n), minpos(n, INF), maxpos(n, -1);
  vector<int> minl(n, INF), maxr(n, -1);

  int id = 0;

  function<void(int)> dfs = [&] (int v){
    used[v] = 1, cid[v] = id;
    minpos[id] = min(minpos[id], v);
    maxpos[id] = max(maxpos[id], v);
    if (!used[p[v]]) dfs(p[v]);
  };

  for (int i = 0; i < n; i++){
    if (used[i]) continue;
    dfs(i);
    id++;
  }

  vector<vector<int>> g(id);

  for (int i = 0; i < id; i++){
    for (int j = minpos[id]; j <= maxpos[id]; j++){
      g[cid[j]].pb(i);
    }
  }

  function<void(int, int)> dfs1 = [&] (int v, int val){
    minl[v] = val;
    for (auto u : g[v]) if (minl[u] == INF) dfs1(u, val);
  };

  function<void(int, int)> dfs2 = [&] (int v, int val){
    maxr[v] = val;
    for (auto u : g[v]) if (maxr[u] == -1) dfs2(u, val);
  };

  vector<int> order(id);
  iota(all(order), 0);

  sort(all(order), [&] (int i, int j){
    return minpos[i] < minpos[j];
  });

  for (auto i : order){
    if (minl[i] == INF) dfs1(i, minpos[i]);
  }

  sort(all(order), [&] (int i, int j){
    return maxpos[i] > maxpos[j];
  });

  for (auto i : order){
    if (maxr[i] == -1) dfs2(i, maxpos[i]);
  }

  vector<vector<int>> dp(n, vector<int>(n, INF));

  dp[minl[cid[s]]][maxr[cid[s]]] = 0;

  ll ans1;

  for (int len = 1; len <= n; len++){
    for (int l = 0; l + len - 1 < n; l++){
      int r = l + len - 1;
      if (dp[l][r] == INF) continue;
      assert(cycleend[r]);
      ans1 = dp[l][r];
      if (l > 0 && !cycleend[l - 1]){
        int newl = min(l, minl[cid[l - 1]]), newr = max(r, maxr[cid[l - 1]]);
        dp[newl][newr] = min(dp[newl][newr], dp[l][r] + 2);
      }
      if (!cycleend[r] && r < n - 1){
        int newl = min(l, minl[cid[r + 1]]), newr = max(r, maxr[cid[r + 1]]);
        dp[newl][newr] = min(dp[newl][newr], dp[l][r] + 2);
      }
    }
  }

  return ans + ans1;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:128:16: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |   return ans + ans1;
      |                ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Runtime error 6 ms 8532 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Runtime error 6 ms 8532 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Runtime error 6 ms 8532 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -