Submission #1077504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077504		jk_	Ancient Books (IOI17_books)	C++14	100 / 100	138 ms	23136 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

struct cycle { int l, r; };

long long minimum_walk(std::vector<int> p, int s) {
  long long d = 0;
  int n = p.size();
  for (int i = 0; i < n; ++i) {
    d += abs(p[i] - i);
  }

  vector<int> c(p.size(), -1);
  vector<cycle> cycles;
  int sl=s, sr=s;
  for (int i = 0; i < n; ++i) {
    if (c[i] != -1) continue;
    if (p[i] == i) continue;
    int x = i;
    int l=x, r=x;
    c[x] = cycles.size();
    while ((x=p[x]) != i) {
      c[x] = cycles.size();
      l = min(l, x);
      r = max(r, x);
    }
    if (l <= s && r >= s){
      sl = min(l, sl);
      sr = max(r, sr);
    }
    cycles.push_back({l, r});
  }

  int l=s, r=s; // already covered
  int lx=s, rx=s; // free extension
  if (c[s] != -1) {
    lx = cycles[c[s]].l;
    rx = cycles[c[s]].r;
  }

  while (l > sl || r < sr) {
    if (l-1 >= 0 && l-1 >= lx)
      --l;
    else if (r+1 < n && r+1 <= rx)
      ++r;
    else {
      l = max(0, l-1);
      r = min(r+1, n-1);
      d += 2;
    }
    if (c[l] != -1) {
      lx = min(lx, cycles[c[l]].l);
      rx = max(rx, cycles[c[l]].r);
    }
    if (c[r] != -1) {
      lx = min(lx, cycles[c[r]].l);
      rx = max(rx, cycles[c[r]].r);
    }
  }
  while (r+1 < n) {
    ++r;
    if (c[r]==-1) continue;
    if (cycles[c[r]].l != cycles[c[r]].r) {
      d += 2*max(0, r - rx);
      rx = max(rx, cycles[c[r]].r);
    }
  }
  while (l-1 >= 0) {
    --l;
    if (c[l]==-1) continue;
    if (cycles[c[l]].l != cycles[c[l]].r) {
      d += 2*max(0, lx - l);
      lx = min(lx, cycles[c[l]].l);
    }
  }

  return d;
}

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