Submission #72840

#	Time	Username	Problem	Language	Result	Execution time	Memory
72840		funcsr	Ancient Books (IOI17_books)	C++17	50 / 100	271 ms	36860 KiB

books

#include "books.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i,n)for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
typedef pair<int, int> P;

int N;
bool used[1000000];
int T[1000000];
vector<int> G[1000000];

long long minimum_walk(vector<int> A, int S) {
  N = A.size();
  vector<P> ps;
  int m = INF,num=0,w=INF;
  int lmost = S, rmost = S;
  rep(i, N) if (!used[i]) {
    if (i == A[i]) continue;
    int x = i;
    int left = x, right = x;
    int ww = INF;
    while (!used[x]) {
      left = min(left, x);
      right = max(x, right);
      ww=min(ww,abs(S-x));

      if (x < A[x]) {
        T[x]++;
        T[A[x]]--;
      }
      used[x] = true;
      x = A[x];
    }
    if (left < S && S < right) lmost = min(lmost, left),num++,w=min(w,ww);
    if (left < S && S < right) rmost = max(rmost, right);
  }

  rep(i,N-1) T[i+1] += T[i];
  long long cost = 0;
  bool yes = false;
  for (int i=N-1; i>=S; i--) {
    if (T[i])yes=true;
    cost += max(T[i], (int)yes);
  }
  yes = false;
  for (int i=0; i<S; i++) {
    if (T[i])yes=true;
    cost += max(T[i], (int)yes);
  }

  /*
  int m = INF;
  int rm = 0;
  for (int left=N-1; left>=0; left--) {
    m = min(m, left+rm);
    for (int r : G[left]) rm = max(rm, r);
  }
  */
  if (num==1) {
    cost += w;
  }
  else if (num >= 2) {
    cost += min(rmost-S, S-lmost);
  }
  return 2LL*cost;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:25:7: warning: unused variable 'm' [-Wunused-variable]
   int m = INF,num=0,w=INF;
       ^

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