Submission #366053

#	Time	Username	Problem	Language	Result	Execution time	Memory
366053		denkendoemeer	Ancient Books (IOI17_books)	C++14	100 / 100	187 ms	19052 KiB

books

#include<bits/stdc++.h>
#include "books.h"
#define ll long long
using namespace std;
ll minimum_walk(vector<int>p,int s)
{
    int n=p.size(),i;
    ll ans=0;
    for(i=0;i<n;i++)
        ans=ans+abs(i-p[i]);
    int minl=n-1,minr=0;
    for(i=0;i<n;i++)
        if (i!=p[i])
            minl=min(minl,i),minr=max(minr,i);
    int nrl=s,nrr=s;
    queue<int>qu;
    qu.push(s);
    while(1){
        while(qu.size()){
            int nod=qu.front();
            qu.pop();
            while(nrl>p[nod]){
                nrl--;
                qu.push(nrl);
            }
            while(nrr<p[nod]){
                nrr++;
                qu.push(nrr);
            }
        }
        int st=nrl,dr=nrr;
        int cntl=0,cntr=0,okl=0,okr=0;
        queue<int>ql,qr;
        while(1){
            if (st<=minl)
                break;
            st--;
            cntl++;
            ql.push(st);
            while(ql.size()){
                int nod=ql.front();
                ql.pop();
                while(st>p[nod]){
                    st--;
                    ql.push(st);
                }
                if (p[nod]>s)
                    okl=1;
            }
            if (okl)
                break;
        }
        while(1){
            if (dr>=minr)
                break;
            dr++;
            cntr++;
            qr.push(dr);
            while(qr.size()){
                int nod=qr.front();
                qr.pop();
                while(dr<p[nod]){
                    dr++;
                    qr.push(dr);
                }
                if (p[nod]<s)
                    okr=1;
            }
            if (okr)
                break;
        }
        if (okl && okr){
            ans=ans+2*min(cntl,cntr);
            while(nrl>st)
                qu.push(--nrl);
            while(nrr<dr)
                qu.push(++nrr);
        }
        else{
            ans=ans+2*(cntl+cntr);
            break;
        }
    }
    return ans;
}

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