Submission #412953

#	Time	Username	Problem	Language	Result	Execution time	Memory
412953		Pichon5	Ancient Books (IOI17_books)	C++17	50 / 100	170 ms	18788 KiB

books

#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define vi vector<int>
using namespace std;


ll minimum_walk(vector<int> p,int s){
   ll res=0;
   int n=p.size();
   vi cant(n+2,0);
   for(int i=0;i<n;i++){
      if(p[i]==i)continue;
      res+=abs(i-p[i]);
      int mi=min(i,p[i]);
      int ma=max(i,p[i]);
      cant[mi]++;
      cant[ma]--;
   }  
   //tengo que marcar los caminos no los nodos
   //0 = (0,1)
   //1=  (1,2);
   int sum=0;
   int acum=0;
   for(int i=0;i<n-1;i++){
      acum+=cant[i];
      if(acum==0){
         sum++;
      }else{
         res+=2*sum;
         sum=0;        
      }
   }
   return res;   
}
/*int main(){
   int n,x;
   cin>>n;
   vi v;
   for(int i=0;i<n;i++){
      cin>>x;
      v.pb(x);
   }
   cout<<minimum_walk(v,0)<<endl;

}*/

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