Submission #396600

#	Time	Username	Problem	Language	Result	Execution time	Memory
396600		usachevd0	Ancient Books (IOI17_books)	C++14	50 / 100	736 ms	150044 KiB

books

#include <bits/stdc++.h>
#ifndef DEBUG
  #include "books.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) {
  return y < x ? (x = y, true) : false; 
}
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}


const int INF32 = 1e9;

ll minimum_walk(vector<int> p, int s) {
  int n = p.size();
  vector<int> p_inv(n);
  for (int i = 0; i < n; ++i) {
    p_inv[p[i]] = i;
  }

  ll Ans = 0;
  for (int i = 0; i < n; ++i) Ans += labs(p[i] - i);

  vector<int> cyc(n, -1);
  vector<int> cl(n, +INF32), cr(n, -INF32);
  int C = 0;
  for (int i = 0; i < n; ++i) {
    if (p[i] != i && cyc[i] == -1) {
      int c = C++;
      cl[c] = cr[c] = i;
      int x = i;
      do {
        cyc[x] = c;
        chkmax(cr[c], x);
        x = p[x];
      } while (x != i);
    }
  }
  if (!C) return 0;

  vector<int> G[C];
  vector<int> GR[C];
  for (int c = 0; c < C; ++c) {
    for (int i = cl[c]; i <= cr[c]; ++i) {
      if (cyc[i] != -1 && cyc[i] != c) {
        G[c].push_back(cyc[i]);
        GR[cyc[i]].push_back(c);
      }
    }
  }

  vector<char> used(C, false);
  vector<int> ord;
  function<void(int)> dfs = [&](int v) {
    used[v] = true;
    for (int& u : G[v])
      if (!used[u])
        dfs(u);
    ord.push_back(v);
  };
  for (int c = 0; c < C; ++c)
    if (!used[c])
      dfs(c);
  reverse(all(ord));
  vector<int> scc(C, -1);
  int S = 0;
  function<void(int)> dfs1 = [&](int v) {
    scc[v] = S;
    for (int& u : GR[v])
      if (scc[u] == -1)
        dfs1(u);
  };
  for (int& v : ord) {
    if (scc[v] == -1) {
      dfs1(v);
      ++S;
    }
  }

  vector<char> src(S, true);
  for (int c = 0; c < C; ++c) {
    for (int d : G[c]) {
      if (scc[c] != scc[d]) {
        src[scc[d]] = false;
      }
    }
  }

  vector<int> sl(S, +INF32), sr(S, -INF32);
  for (int c = 0; c < C; ++c) {
    int s = scc[c];
    chkmin(sl[s], cl[c]);
    chkmax(sr[s], cr[c]);
  }
  vector<pii> segs;
  for (int s = 0; s < S; ++s) {
    if (src[s]) {
      segs.emplace_back(sl[s], sr[s]);
    }
  }
  sort(all(segs));
  for (int i = 0; i + 1 < segs.size(); ++i) {
    int r1 = segs[i].se;
    int l2 = segs[i + 1].fi;
    assert(r1 < l2);
    Ans += 2 * (l2 - r1);
  }
  bool inside = false;
  for (auto& g : segs) {
    if (g.fi <= s && s <= g.se) {
      inside = true;
      break;
    }
  }
  if (!inside) {
    if (s < segs[0].fi) {
      return Ans + 2 * labs(segs[0].fi - s);
    } else if (s > segs.back().se) {
      return Ans + 2 * labs(s - segs.back().se);
    } else {
      return Ans;
    }
  } else {
    int Add = INF32;
    {
      int l = s;
      while (cyc[l] == -1 || !src[scc[cyc[l]]]) --l;
      if (l == s) return Ans;
      /*vector<int> dp(n, 0);
      for (int j = s - 1; j > l; --j) {
        dp[j] = dp[j + 1];
        if (p[j] != j && j < p_inv[j] && p_inv[j] <= s) {
          chkmax(dp[j], p_inv[j] - j + dp[p_inv[j]]);
        }
      }
      vector<int> dq(n, 0);
      for (int j = l + 1; j <= s; ++j) {
        dq[j] = dq[j - 1];
        if (p[j] != j && l < p_inv[j] && p_inv[j] < j) {
          chkmax(dq[j], j - p_inv[j] + dq[p_inv[j]]);
        }
      }*/
      vector<int> cc(n, 0);
      /*for (int c = 0; c < C; ++c) {
        if (l < cl[c] && cl[c] <= s) {
          for (int i = cl[c]; i < min(cr[c], s); ++i) {
            cc[i] = 1;
          }
        }
      }*/
      for (int i = l + 1; i <= s; ++i) {
        if (1 || l < p[i] && p[i] <= s) {
          for (int j = max(l + 1, min(i, p[i])); j < min(max(i, p[i]), s); ++j) cc[j] = 1;
        }
      }
      chkmin(Add, 2 * (s - l) - 2 * accumulate(all(cc), 0));
    }
    {
      int r = s;
      while (cyc[r] == -1 || !src[scc[cyc[r]]]) ++r;
      if (r == s) throw;
      /*vector<int> dp(n, 0);
      for (int j = s + 1; j < r; ++j) {
        dp[j] = dp[j - 1];
        if (p[j] != j && s <= p_inv[j] && p_inv[j] < j) {
          chkmax(dp[j], j - p_inv[j] + dp[p_inv[j]]);
        }
      }
      debug(r - s, dp[r - 1]);*/
      vector<int> cc(n, 0);
      for (int c = 0; c < C; ++c) {
        if (s <= cr[c] && cr[c] < r) {
          for (int i = max(s, cl[c]); i < cr[c]; ++i) {
            cc[i] = 1;
          }
        }
      }
      //chkmin(Add, 2 * (r - s) - 2 * accumulate(all(cc), 0));
    }
    return Ans + Add;
  }

  /*
  if (s != 0) {
    bool inside = false;
    for (pii g : segs) {
      if (g.fi <= s && s <= g.se) {
        inside = true;
      }
    }
    return (ll)inside;
  }
  /**/
  return Ans;
}


#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, s;
  cin >> n >> s;
  vector<int> p(n);
  for (auto& x : p) cin >> x;
  cout << minimum_walk(p, s) << '\n';
    
  return 0;
}
#endif

Compilation message (stderr)

books.cpp:238:3: warning: "/*" within comment [-Wcomment]
  238 |   /**/
      |    
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:147:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |   for (int i = 0; i + 1 < segs.size(); ++i) {
      |                   ~~~~~~^~~~~~~~~~~~~
books.cpp:197:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  197 |         if (1 || l < p[i] && p[i] <= s) {
      |                  ~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30