Submission #1239623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239623		vivkostov	Ancient Books (IOI17_books)	C++20	50 / 100	113 ms	35396 KiB

books

//#pragma once
//#include "grader.cpp"
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
    int l,r;
    long long int st;
};
bool cmp(cell a1,cell a2)
{
    return a1.l<a2.l;
}
int n,s,br,mid,used[1000005],a[1000005],ind[1000005],f1,f2;
long long int otg=0;
cell p[1000005];
void dfs(int beg)
{
    p[br].l=min(p[br].l,beg);
    p[br].r=max(p[br].r,beg);
    p[br].st+=abs(a[beg]-beg);
    ind[beg]=br;
    used[beg]=1;
    if(!used[a[beg]])
    {
        dfs(a[beg]);
    }
}
void prec()
{
    for(int i=1; i<=n; i++)
    {
        if(!used[i])
        {
            br++;
            p[br].l=1e9;
            dfs(i);
            otg+=p[br].st;
        }
    }
    memset(used,0,sizeof(used));
    sort(p+1,p+br+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            f1=i;
            break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(a[i]!=i)
        {
            f2=i;
            break;
        }
    }
}
void resh()
{
    int tol=s,tor=s+1,l=s,r=s,i1,i2;
    long long int dobl=0,dobr=0,dob=0,br=0;
    while(true)
    {
        if(tol==0&&tor==n+1)break;
        i1=ind[tol];
        i2=ind[tor];
        //cout<<i1<<" "<<i2<<" "<<tol<<" "<<tor<<endl;
        br++;
        if(br==1000000)
        {
            otg=tor;
            return;
        }
        if(used[i1])
        {
            tol--;
            continue;
        }
        if(used[i2])
        {
            tor++;
            continue;
        }
        if(tol>0&&p[i1].r<=s)
        {
            if(p[i1].l!=p[i1].r)
            {
                if(l>tol)dobl+=l-tol;
                l=min(l,p[i1].l);
            }
            used[i1]=1;
            tol--;
        }
        if(tor<n+1&&p[i2].l>s)
        {
            if(p[i2].l!=p[i2].r)
            {
                if(r<tor)dobr+=tor-r;
                r=max(r,p[i2].r);
            }
            used[i2]=1;
            tor++;
        }
        if(i1==i2)
        {
            if(l>tol)dobl+=l-tol;
            if(r<tor)dobr+=tor-r;
            dob+=min(dobl,dobr);
            dobl=0;
            dobr=0;
            l=min(l,p[i1].l);
            r=max(r,p[i2].r);
            used[i1]=1;
            tol--;
            tor++;
        }
    }
    otg+=(dobl+dobr+dob)*2;
}
long long minimum_walk(std::vector<int> p, int S)
{
    n=p.size();
    s=S+1;
    for(int i=1; i<=n; i++)
    {
        a[i]=p[i-1]+1;
    }
    prec();
    resh();
    return otg;
}

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