Submission #827243

#	Time	Username	Problem	Language	Result	Execution time	Memory
827243		vnm06	Ancient Books (IOI17_books)	C++14	100 / 100	91 ms	22848 KiB

books

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

int n, val=1;
int a[1000005];

int ls, rs;
int le, ri;
stack<int> st;

void dfs(int v)
{
    st.push(v);
    while(!st.empty())
    {
        v=st.top();
        ///used[v]=val;
        st.pop();
        v=a[v];
        if(v<le)
        {
            for(int i=v; i<le; i++) st.push(i);
            le=v;
        }
        else if(ri<v)
        {
            for(int i=ri+1; i<=v; i++) st.push(i);
            ri=v;
        }
    }
}

long long minimum_walk(std::vector<int> p, int s)
{
    long long ans=0;
    n=p.size();
    for(int i=0; i<n; i++)
    {
        a[i]=p[i];
        int st=a[i]-i;
        if(st<0) ans-=st;
        else ans+=st;
    }
    int le_gr=0, ri_gr=n-1;
    while(le_gr<s && a[le_gr]==le_gr) le_gr++;
    while(ri_gr>s && a[ri_gr]==ri_gr) ri_gr--;
    ls=0, rs=0;
    le=s, ri=s;
    int obsht=0;
    dfs(s);
    while(le>le_gr || ri<ri_gr)
    {
        if(le==le_gr)
        {
            rs++;
            ri++;
            dfs(ri);
        }
        else if(ri==ri_gr)
        {
            le--;
            ls++;
            dfs(le);
        }
        else
        {
            int tle=le, tri=ri;
            if(ls<rs)
            {
                le--;
                ls++;
                dfs(le);
                if(tri!=ri)
                {
                    obsht=ls;
                    rs=ls;
                }
            }
            else
            {
                ri++;
                rs++;
                dfs(ri);
                if(tle!=le)
                {
                    obsht=rs;
                    ls=rs;
                }
            }
        }
    }
	return ans+2*(ls+rs-obsht);
}

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