Submission #813479

#	Time	Username	Problem	Language	Result	Execution time	Memory
813479		erray	Ancient Books (IOI17_books)	C++17	50 / 100	100 ms	18764 KiB

books

#include "books.h"
//author: erray
#include <bits/stdc++.h>

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif


long long minimum_walk(std::vector<int> p, int s) {
  int N = int(p.size());
	assert(s == 0);
  long long res = 0;
  int l = 0, r = N - 1;
  while (l < N && p[l] == l) {
    ++l;
  }
  while (r >= 0 && p[r] == r) {
    --r;
  }
  if (l == N) {
    return 0;
  }
  res += 2 * l;
  vector<int> upd(N);
  for (int i = 0; i < N; ++i) {
    int L = p[i], R = i;
    if (L > R) {
      swap(L, R);
    }
    upd[L] += 1;
    upd[R] -= 1;  
    res += (R - L);
  }
  for (int i = 0; i < N - 1; ++i) {
    upd[i + 1] += upd[i];
  }
  for (int i = l; i < r - 1; ++i) {
    if (upd[i] == 0) {
      res += 2;
    }
  }
  return res;
}

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