Submission #1239033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239033		vivkostov	Ancient Books (IOI17_books)	C++20	50 / 100	157 ms	31560 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,start,br,used[1000005],a[1000005];
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);
    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;
        }
    }
    sort(p+1,p+br+1,cmp);
    /*for(int i=1;i<=br;i++)
    {
        cout<<p[i].l<<" "<<p[i].r<<" "<<p[i].st<<endl;
    }*/
}
void resh()
{
    int to=1;
    for(int i=1;i<=n;i++)
    {
        if(p[i].l==p[i].r)continue;
        if(to>=p[i].l)
        {
            to=max(to,p[i].r);
        }
        else
        {
            otg+=(p[i].l-to)*2;
            to=p[i].r;
        }
    }
}
long long minimum_walk(std::vector<int> p, int s)
{
    n=p.size();
    for(int i=1;i<=n;i++)
    {
        a[i]=p[i-1]+1;
    }
    start=s;
    prec();
    resh();
	return otg;
}

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