Submission #54991

#	Time	Username	Problem	Language	Result	Execution time	Memory
54991		fallingstar	Ancient Books (IOI17_books)	C++14	100 / 100	435 ms	183180 KiB

books

#include "books.h"
#include <algorithm>

#define long long long

using namespace std;

const int N = 1e6 + 2;

vector<int> p;
int gr[N], boundL[N], boundR[N];

void Dfs(int u) 
{ 
    if (gr[p[u]] == -1) 
    {
        gr[p[u]] = gr[u];
        Dfs(p[u]);         
    }
    boundL[gr[u]] = min(boundL[gr[u]], u);
    boundR[gr[u]] = max(boundR[gr[u]], u);
}

long minimum_walk(std::vector<int> p_, int s) {
    p = p_;
	int n = p.size(), L = 0, R = n - 1;
    while (R > s && p[R] == R) --R;
    while (L < s && p[L] == L) ++L;
    
    fill(gr + L, gr + R + 1, -1);
    for (int i = 0; i < n; ++i)
        boundL[i] = n, boundR[i] = 0;
    
    long ans = 0;
    for (int i = L; i <= R; ++i)
    {
        if (gr[i] == -1) gr[i] = i, Dfs(i);
        ans += abs(i - p[i]);
    }

    int curL = s, curR = s;
    while (curL != L || curR != R)
    {
        int newL, newR;
        if (curL > boundL[gr[s]] || curR < boundR[gr[s]])     // first time
        {
            newL = boundL[gr[s]], newR = boundR[gr[s]];
        }
        else 
        {
            ans += 2;
            newL = curL - (curL > L), newR = curR + (curR < R);            
        }
        while (curL != newL || curR != newR)
        {
            if (curL > newL)
            {
                --curL;
                newL = min(newL, boundL[gr[curL]]);
                newR = max(newR, boundR[gr[curL]]);
            }
            else 
            {
                ++curR;
                newL = min(newL, boundL[gr[curR]]);
                newR = max(newR, boundR[gr[curR]]);
            }
        }
    }
    int valL = 0, valR = 0;
    for (int i = L, mx = 0; i < s; ++i)
    {
        mx = max(mx, p[i]);
        if (mx == i) valL += 2;
    }
    for (int i = R, mn = n; i > s; --i)
    {
        mn = min(mn, p[i]);
        if (mn == i) valR += 2;
    }
    return ans + min(valL, valR);
}

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