Submission #207995

#	Time	Username	Problem	Language	Result	Execution time	Memory
207995		AlexLuchianov	Ancient Books (IOI17_books)	C++14	12 / 100	5 ms	380 KiB

books

#include "books.h"
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>

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 perm[1 + nmax], seen[1 + nmax];

void markcycle(int node, int color, pair<int,int> &interval){
  seen[node] = color;
  interval.first = min(interval.first, node);
  interval.second = max(interval.second, node);
  if(seen[perm[node]] == 0)
    markcycle(perm[node], color, interval);
}

int dist(pair<int,int> a, pair<int,int> b){
  return max(0, max(a.first, b.first) - min(a.second, b.second));
}

long long minimum_walk(std::vector<int> p, int start) {
  int n = p.size();
  for(int i = 0; i < n; i++)
    perm[i] = p[i];
  pair<int,int> orig(start, start);
  markcycle(start, 2, orig);
  ll result = 0;

  for(int i = 0; i < n; i++)
    result += fabs(perm[i] - i);

  vector<pair<int,int>> weak;
  for(int i = 0; i < n; i++)
    if(seen[i] == 0 && perm[i] != i) {
      pair<int,int> newinterval(i, i);
      markcycle(i, 1, newinterval);
      weak.push_back(newinterval);
    }
  sort(weak.begin(), weak.end());

  while(1 < weak.size()){
    pair<int,int> st1 = weak.back();
    weak.pop_back();
    pair<int,int> st2 = weak.back();
    weak.pop_back();
    result += dist(st1, st2) * 2;
    weak.push_back({min(st1.first, st2.first), max(st1.second, st2.second)});
  }

  set<int> destinations;
  for(int i = 0; i < n; i++)
    if(seen[i] == 1)
      destinations.insert(i);
  int bonus = nmax;
  if(destinations.size() == 0)
    bonus = 0;

  for(int i = orig.first; i <= orig.second; i++){
    set<int>::iterator it = destinations.lower_bound(i);
    if(it != destinations.end())
      bonus = min(bonus, (int)fabs(*it - i));
    if(it != destinations.begin()) {
      it--;
      bonus = min(bonus, (int)fabs(*it - i));
    }
  }

	return result + bonus * 2;
}

/*
4 0
0 2 3 1

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

5 2
1 0 2 4 3

5 1
3 0 2 1 4

6 2
5 1 2 3 4 0
*/

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