제출 #207594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207594		AlexLuchianov	고대 책들 (IOI17_books)	C++14	0 / 100	5 ms	376 KiB

books

#include "books.h"
#include <cmath>
#include <iostream>
using namespace std;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
using ll = long long;

int const nmax = 1000000;
int sumright[1 + nmax], sumleft[1 + nmax];

long long minimum_walk(std::vector<int> p, int start) {
  int n = p.size();
  ll result = 0;

  for(int i = 0; i < n; i++){
    result += fabs(p[i] - i);
    if(i < p[i]){
      sumright[i]++;
      sumright[p[i]]--;
    } else if(p[i] < i){
      sumleft[i - 1]++;
      if(0 <= p[i])
        sumleft[p[i] - 1]--;
    }
  }
  for(int i = 1; i < n; i++)
    sumright[i] += sumright[i - 1];
  for(int i = n - 1; 0 <= i; i--)
    sumleft[i] += sumleft[i + 1];

  int last = -1;

  for(int i = start; i < n; i++){
    if(0 < sumright[i]){
      if(start != -1)
        result += 2 * (i - 1 - last);
      last = i;
    }
  }
  last = -1;
  for(int i = start - 1; 0 <= i; i--){
    if(0 < sumright[i]){
      if(start != -1)
        result += 2 * (last - (i + 1));
      last = i;
    }
  }


  int bonus = nmax;
  if(result == 0)
    bonus = 0;
  for(int i = 0; i < n; i++)
    if(i != p[i])
      bonus = min(bonus, (int)fabs(start - i));
	return result + bonus * 2;
}

/*
10 0
0 2 1 3 4 5 6 7 9 8

5 1
3 0 2 1 4

6 2
5 1 2 3 4 0
*/

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