Submission #1239093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239093		Joon_Yorigami	Ancient Books (IOI17_books)	C++17	50 / 100	194 ms	36188 KiB

books

/*
                                                                   .:-=++***#***+=:.
                                                       .:-==+**##**%########***#####*=:.
                                                   .-+#%%#*****############**#******#####+=:
                                                .-*%#####********###########*********#######*+-:
                                              :+#######**********########*****+********##########+-.
                                            :+##########**###******##********************###########+:
                                          :+##########*****#*******###**********************###***####*:
                                        .=###########***###*******#***************************#****#####*:
                                       :*#################******************************************######=
                                      -###################***************+****************************#####*:
                                    .=###################******************************************#****#####+.
                                   :*###################*******************************+************#*****#####:
                                  =#############**######*****#*******************++***++++++***************#####=
                                .*###########******####*****#************+++*+**+++***++++++++***#**********#####+
                               -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
                              =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
                            .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
                           .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
               .:-:       .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
           .--:++=+.     .**.  ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
           :++=====     .**.  -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
            .-=++=      =*.   +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
                .      .#.   .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
                       --    -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
         -=+++-.       =     +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
       .++====++       =     ####################**##*****###***#+****#=#****  .+*###************+  ##   +***######****##########+--+#%%%%+:
  .---:=+======+:      +.    ##################%#***#*****####****#**#+-####.  .+###***##*******#  .#:   :***########***##%%%####%#=. .:=*%%
 ---==++=======+=      -=   .%#################%****#*****######-#*##*.=%#*.    +=---:::.......:   =:     =**#########***#%%%%%%%%%%%=.   .-
 :-:===========+=      .#.  :%################%%****#*****#####= :-+***#*=.                               .*#########%%#**#*=%%%%%%%%%%=.
  .---=========+=       :*. -#################%%****#*****%#+-.-*#%%%@###*=                                +##########%%%***:+-#%%%#####*:
    .:=++++====+-        =*.=###%############%@%****#*****#. =###%%%@@@+                                   ###########%%%%#*#:  -*########=
        ..:::::-.         +*+###%####%######%%+******#****#=##= -@@@@@@@+                                 =*###########%%%%##+    :*#######+
                           =%##+%####%######%+.******#*****%%#-:+@@@@%-=*                                 +..###########%##%%%*.    -#######
                            %##=#####%###%%#%:=******#*****%*.**##*+=:  .                   -+**####*=:  -  .=###############%%*:    .+#####
                           .%###%########%%%%:.#*****##*****= .+:      .                   :-::.:--=++-  :  .-*##################+:    :####
                           :##.*###########%@# #************+   .:.-==--                                .    +**###+*##############*:   .*##
                           -%- ############%@@-#*###*#=##***#.                                          :.  =*++*#**++*##############*-  .##
                           =#  ############@@@######*#:###*##=                                          :..+*++++***+++++*##############=.+#
                           +:  ###########%@%%%%######.=######                                         .=+#+++++++***+++++****##############
                          .+   *##########%%%%%%######::######=                                        =+++#*+++++++*#+++++******###########
                          +:   =%#%######%%%##%@######:-+######.              .:------==              :*++++**+++++++*#*+++++********#######
                         -*    :%%%%#####%%%##%%%#####***######*             -=--------=:            -*+++++++*++++++++*#**+++*=:=******+==*
                        .*+     +%%%%###%%####%%%#####**+#######=            -........:=:          -++++++++++*#**##***+******++- .-******=.
                        -*=      *%%%%##%%%%%%%#%#####**++#######.           :.........-        .=#%%%######%##########%#+*******.  .-++++*+
                        -*+     .*%%%%#%%#######%#####*++++######*:           .........      :=#%@@%%%%%%#################*++*****=.  .-++++
                        :**.   :###%%%#%%########%####*++++*#######=-:..                  -+#%%%###########################++++****#=.  .-++
                         -*+  .######%%%%#########%###@@@%%%%######+...:----:.         :*%################################%*+++++*+###-   .+
                          :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+.  .
                            -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*.  =##+
                             +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++    -##.
                            =%**********#######%%###############%*#####=...=.        .  :-=-: .###############%#******####%#####+=     +*
                            *#************#############%%#######**+*%####-.-                .-:=##############%*********##%#######=:  .+.
                            *#****************##**######%%%###*:   ::*#####:     -::            .-+####%%%####%*********#%##########*-:
                            =#***********************######%*-        .--:=:.   =. :--:             .-=*###%###*********#######*#######+-
                            .#**************************###=             .:.  ::...   .=.               +***#%##*******#########***#######+:
                             =##**************************:      :-:--.  .. .+.....     +               =******#%#####%##########***#####**#
                              ####**********************+.    . :#########+-=:....      -:              +***********##%%#***######****##****
                              .#%####******************-        *##########*:....... ...:.              #**************##*********###*##****
                               :#%@%%%###*************          =#*******####+....... :-.              *#***************%************#%#****
                              .#**###%%%%%######****#.           =#***********#=....:-.              :*#****************##*************####*
                              *#**#****#####%%%%#####             =#*************+=:       .=-::..:-*#*****************##*****************##
                             -#***#*******######%%%%=               :=*#**********:    ...  ##*##%##*******************#********************
                            .%*****#*********######%.                    ....:-=*-  :++:   =#****##%####*************###********************
:.                          +#*****#**********####%+                            ..-*#***#+=##*******##%%###********####*********************
 .:-:.                     .%#*****#**********#%%%*                  :=+**##########******###********#%%%%%%##****###***********************
     --                    =%#******#*********@#%%-.               :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-.   .=.                  ##*******#********#%#**###*+=-:.:     -######%##%###%####%%%%%##########%####%%%%##%*************####************
====   .=                 :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
 ====   -:                *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
 :+=+.   =               .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
using vll = vector<long long>;

long long minimum_walk(std::vector<int> p, int s)
{
  ll n = p.size();
  ll ans=0;
  for(int i=0;i<n;i++)
  {
    ans+=abs(p[i]-i);
  }
  vll target;
  for(auto owo:p)
  	target.push_back(owo);
  vector<bool> visited(n,false);
  vll rightmost(n,0);
  ll curr;
  for(int i=0;i<n;i++)
  {
    if(visited[i])
      continue;
    stack<ll> q;
    vll cycle;
    q.push(i);
    while(!q.empty())
    {
      curr=q.top();
      q.pop();
      if(visited[curr])
        continue;
      visited[curr]=true;
      cycle.push_back(curr);
      if(!visited[target[curr]])
        q.push(target[curr]);
    }
    ll maxi=*max_element(cycle.begin(),cycle.end());
    for(auto idx:cycle)
      rightmost[idx]=maxi;
  }
  curr=0;
  ll last_unsorted=n-1;
  while(last_unsorted>=0 && target[last_unsorted]==last_unsorted)
    last_unsorted-=1;
  for(int i=0;i<last_unsorted;i++)
  {
    if(curr<i)
      ans+=2;
    curr=max(curr,rightmost[i]);
  }
  return ans;
}

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