Submission #293847

#	Time	Username	Problem	Language	Result	Execution time	Memory
293847		Bruteforceman	Ancient Books (IOI17_books)	C++11	50 / 100	236 ms	20572 KiB

books

#include "bits/stdc++.h"
#include "books.h"
using namespace std;

long long minimum_walk(std::vector<int> p, int s) {
  int n = p.size();
  long long ans = 0;
  vector <bool> vis (n, false);
  vector <pair <int, int>> range;
  for(int i = 0; i < n; i++) ans += abs(p[i] - i);
  for(int i = 0; i < n; i++) {
    if(vis[i] == true) continue;
    vector <int> cycle;
    int cur = i;
    do {
      vis[cur] = true;
      cycle.push_back(cur);
      cur = p[cur];
    } while(vis[cur] == false);
    range.emplace_back(*min_element(cycle.begin(), cycle.end()),
                       *max_element(cycle.begin(), cycle.end()));
  }
  vector <int> pre (n, 0); 
  for(auto i : range) {
    pre[i.second] -= 1;
    pre[i.first] += 1;
  }
  for(int i = 1; i < pre.size(); i++) pre[i] += pre[i - 1];
  ans += count(pre.begin(), pre.end(), 0) * 2;
  for(int i = pre.size() - 1; i >= s; i--) {
    if(pre[i] == 1) break;
    ans -= 2;
  }
  for(int i = 0; i < s; i++) {
    if(pre[i] == 1) break;
    ans -= 2;
  }
  int opt = INT_MAX;
  for(int i = 0; i < n; i++) {
    if(p[i] != i) {
      opt = min(opt, abs(i - s));
    }
  }
  if(opt < INT_MAX) {
    if(s > 0 && pre[s - 1] > 0) {
      if(pre[s] > 0) {
        ans += 2 * opt;
      }
    }
  }
  return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 1; i < pre.size(); i++) pre[i] += pre[i - 1];
      |                  ~~^~~~~~~~~~~~

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