Submission #207207

#	Time	Username	Problem	Language	Result	Execution time	Memory
207207		AlexLuchianov	고대 책들 (IOI17_books)	C++14	50 / 100	219 ms	22812 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 active = 0;
  for(int i = n; start <= i; i--){
    active |= (0 < sumright[i]);
    active |= (0 < sumleft[i]);

    if(0 == sumright[i] && 0 == sumleft[i])
      result += active * 2;
    else
      result += fabs(sumright[i] - sumleft[i]);
  }
  active = 0;
  for(int i = 0; i < start; i++){
    active |= (0 < sumright[i]);
    active |= (0 < sumleft[i]);

    if(0 == sumright[i] && 0 == sumleft[i])
      result += active * 2;
    else
      result += fabs(sumright[i] - sumleft[i]);
  }
	return result;
}
/*
6 0
0 1 2 5 4 3
*/

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