Submission #208872

#	Time	Username	Problem	Language	Result	Execution time	Memory
208872		rama_pang	Ancient Books (IOI17_books)	C++14	100 / 100	261 ms	26748 KiB

books

#include "books.h"

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

using lint = long long;

void extend(int &l, int &r, vector<int> &C, vector<int> &L, vector<int> &R) {
  int ll = min({l, L[C[l]], L[C[r]]});
  int rr = max({r, R[C[l]], R[C[r]]});

  while (ll < l || r < rr) {
    if (ll < l) l--;
    if (r < rr) r++;
    ll = min({ll, L[C[l]], L[C[r]]});
    rr = max({rr, R[C[l]], R[C[r]]});
  }
}

int connect(int l, int r, int target_l, int target_r, vector<int> &C, vector<int> &L, vector<int> &R) {
  int cost = 0;
  do {
    extend(l, r, C, L, R);

    int cost_l = 0, cost_r = 0;

    bool next_l = false;
    int l_l = l, r_l = r;
    while (true) {
      if (l_l <= target_l) break;
      l_l--;
      cost_l += 2;
      extend(l_l, r_l, C, L, R);
      if (r < r_l) {
        next_l = true;
        break;
      }
    }

    bool next_r = false;
    int l_r = l, r_r = r;
    while (true) {
      if (target_r <= r_r) break;
      r_r++;
      cost_r += 2;
      extend(l_r, r_r, C, L, R);
      if (l_r < l) {
        next_r = true;
        break;
      }
    }

    if (next_l && next_r) {
      cost += min(cost_l, cost_r); // walking to shortest one, since the cycles overlap we need no additional cost
    } else {
      cost += cost_l + cost_r; // we must walk both ways
    }

    l = min(l_l, l_r);
    r = max(r_l, r_r);

  } while (target_l < l || r < target_r);

  return cost;
}

lint minimum_walk(vector<int> p, int s) {
  lint ans = 0;
  int n = p.size();

  vector<int> cycle(n, -1);
  vector<int> L, R; // left and rightmost books in cycle
  int c = 0; // cycle count

  int target_l = s, target_r = s;
  for (int i = 0; i < n; i++) {
    ans += abs(i - p[i]);
    if (cycle[i] == -1) {
      L.emplace_back(i);
      R.emplace_back(i);

      int j = i;
      do {
        cycle[j] = c;
        L[c] = min(L[c], j);
        R[c] = max(R[c], j);
        j = p[j];
      } while (j != i);

      if (p[i] != i) {
        target_l = min(target_l, L[c]);
        target_r = max(target_r, R[c]);
      }

      c++;
    }
  }

  return ans + connect(s, s, target_l, target_r, cycle, L, R);
}

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