Submission #1278431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278431		MMihalev	Ancient Books (IOI17_books)	C++20	50 / 100	95 ms	23784 KiB

books

#include<iostream>
#include<vector>
#include "books.h"
using namespace std;
const int MAX_N=1e6+6;
int col[MAX_N];
int cols;
int a[MAX_N];
int l[MAX_N];
int r[MAX_N];
int n;
long long ans;
long long minimum_walk(std::vector<int> p, int s)
{
    n=p.size();
    s++;
    bool zero=1;
    for(int i=1;i<=n;i++)
    {
        l[i]=1e9;
        r[i]=-1;

        a[i]=p[i-1]+1;

        if(a[i]!=i)zero=0;
    }

    if(zero)return 0;

    int b=1,e=n;
    while(a[e]==e)e--;
    while(a[b]==b)b++;

    ans+=(b-1)*2;

    for(int i=b;i<=e;i++)
    {
        ans+=abs(i-a[i]);
        if(col[i]==0)
        {
            if(i==a[i])continue;
            cols++;
            int pos=i;
            while(col[pos]==0)
            {
                l[cols]=min(l[cols],pos);
                r[cols]=max(r[cols],pos);
                col[pos]=cols;
                pos=a[pos];
            }
        }
    }

    int active=0;
    for(int i=b;i<=e;i++)
    {
        if(i>b && active==0)
        {
            ans+=2;
        }

        int curcol=col[i];
        if(l[curcol]==i)
        {
            active++;
        }
        if(r[curcol]==i)active--;
    }

	return ans;
}

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