Submission #122089

#	Time	Username	Problem	Language	Result	Execution time	Memory
122089		nvmdava	Ancient Books (IOI17_books)	C++17	100 / 100	151 ms	15052 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long res;
long long minimum_walk(std::vector<int> p, int s){
   while(!p.empty() && p.back() == p.size() - 1)
      p.pop_back();
   if(p.empty()) return 0;
   int n = p.size();
   if(s >= n){
      res += (s - n + 1) << 1;
      s = n - 1;
   }
   reverse(p.begin(), p.end());
   s = n - 1 - s;
   for(int i = 0; i < n; i++)
      p[i] = n - 1 - p[i];

   while(p.back() == p.size() - 1)
      p.pop_back();
   n = p.size();
   if(s >= n){
      res += (s - n + 1) << 1;
      s = n - 1;
   }
   int tmn = s, tmx = s;
   for(int i = 0; i < n; i++){
      res += abs(p[i] - i);
      if(1LL * (tmx - p[i]) * (tmx - i) <= 0 || 1LL * (tmn - p[i]) * (tmn - i) <= 0){
         tmx = max(tmx, max(i, p[i]));
         tmn = min(tmn, min(i, p[i]));
      }
   }
   int l = s, r = s, mn = min(s, p[s]), mx = max(s, p[s]);
   while(l != tmn || r != tmx){
      if(l != tmn ){
         l--;
         tmn = min(tmn, p[l]);
         tmx = max(tmx, p[l]);
      } else {
         r++;
         tmn = min(tmn, p[l]);
         tmx = max(tmx, p[l]);
      }
   }


   l = r = s;
   while(l != mn || r != mx){
      if(l != mn){
         l--;
         mn = min(mn, p[l]);
         mx = max(mx, p[l]);
      } else {
         r++;
         mn = min(mn, p[r]);
         mx = max(mx, p[r]);
      }
   }
   while(mn != tmn || mx != tmx){
      res += 2;
      if(mn != tmn)mn--;
      if(mx != tmx)mx++;
      while(l != mn || r != mx){
         if(l != mn){
            l--;
            mn = min(mn, p[l]);
            mx = max(mx, p[l]);
         } else {
            r++;
            mn = min(mn, p[r]);
            mx = max(mx, p[r]);
         }
      }
   }
   for(; l >= 0; l--){
      if(mn > l) res += 2;
      mn = min(mn, p[l]);
   }
   for(; r < n; r++){
      if(mx < r) res+= 2;
      mx = max(mx, p[r]);
   }
   return res;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(!p.empty() && p.back() == p.size() - 1)
                        ~~~~~~~~~^~~~~~~~~~~~~~~
books.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p.back() == p.size() - 1)
          ~~~~~~~~~^~~~~~~~~~~~~~~

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