Submission #94567

#	Time	Username	Problem	Language	Result	Execution time	Memory
94567		wxh010910	Ancient Books (IOI17_books)	C++17	100 / 100	147 ms	19072 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

long long minimum_walk(vector<int> p, int s) {
  int n = p.size();
  int l = n, r = -1;
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    if (i != p[i]) {
      ans += abs(i - p[i]);
      l = min(l, i);
      r = max(r, i);
    }
  }
  int cur_l = s, cur_r = s;
  queue<int> q;
  q.push(s);
  while (true) {
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      while (cur_l > p[x]) {
        q.push(--cur_l);
      }
      while (cur_r < p[x]) {
        q.push(++cur_r);
      }
    }
    int new_l = cur_l, new_r = cur_r;
    int cost_l = 0, cost_r = 0;
    bool found_l = false, found_r = false;
    while (new_l > l && !found_l) {
      q.push(--new_l);
      ++cost_l;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (p[x] > s) {
          found_l = true;
        }
        while (new_l > p[x]) {
          q.push(--new_l);
        }
      }
    }
    while (new_r < r && !found_r) {
      q.push(++new_r);
      ++cost_r;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (p[x] < s) {
          found_r = true;
        }
        while (new_r < p[x]) {
          q.push(++new_r);
        }
      }
    }
    if (found_l && found_r) {
      ans += min(cost_l, cost_r) << 1;
      while (cur_l > new_l) {
        q.push(--cur_l);
      }
      while (cur_r < new_r) {
        q.push(++cur_r);
      }
    } else {
      ans += cost_l + cost_r << 1;
      break;
    }
  }
  return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:71:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       ans += cost_l + cost_r << 1;
              ~~~~~~~^~~~~~~~

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