Submission #283273

#	Time	Username	Problem	Language	Result	Execution time	Memory
283273		MKopchev	Ancient Books (IOI17_books)	C++14	50 / 100	211 ms	16376 KiB

books

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

const int nmax=1e6+42;

int go_left[nmax],go_right[nmax];

long long minimum_walk(std::vector<int> p, int s)
{
    int n=p.size();

	int maxi_right=s,mini_left=s;

	for(int i=0;i<n;i++)
        if(i!=p[i])
        {
            maxi_right=max(maxi_right,i);
            maxi_right=max(maxi_right,p[i]);

            mini_left=min(mini_left,i);
            mini_left=min(mini_left,p[i]);

            if(i<p[i])go_left[i]++,go_left[p[i]]--;
            else go_right[p[i]]++,go_right[i]--;
        }

    for(int i=1;i<n;i++)
    {
        go_left[i]+=go_left[i-1];
        go_right[i]+=go_right[i-1];
    }

    long long outp=0;

    for(int i=mini_left;i<maxi_right;i++)
    {
        //cout<<i<<" -> "<<go_left[i]<<" "<<go_right[i]<<endl;

        if(go_left[i]==0&&go_right[i]==0)outp+=2;
        else outp+=2*max(go_left[i],go_right[i]);
    }

    return outp;
}

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