제출 #475606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475606		blue	고대 책들 (IOI17_books)	C++17	100 / 100	194 ms	30652 KiB

books

#include "books.h"
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;

const int maxN = 1'000'000;

int N;
int S;
vector<int> P;

int curr_cycle = -1;
vector<int> cycle(maxN, -1);
vector<int> L(maxN, 1+maxN);
vector<int> R(maxN, -1);

int target_L, target_R;

void extend(int& l, int& r) //all extensions in [l+1, r-1] have already been done
{
    int new_l = l;
    int new_r = r;

    while(1)
    {
        new_l = min(new_l, min(L[cycle[l]], L[cycle[r]]));
        new_r = max(new_r, max(R[cycle[l]], R[cycle[r]]));

        if(new_l < l)
            l--;
        else if(r < new_r)
            r++;
        else
            break;
    }
}

bool left_cover;
long long left_cost;

void trial_left(int& l, int& r) //l, r is fully extended,    extend it further
{
    left_cost = 0;

    if(l == target_L)
    {
        left_cover = 0;
        left_cost = 0;
    }
    else
    {
        int target = l-1;
        while(target_L <= target && R[cycle[target]] < S)
            target--;

        if(target < target_L) left_cover = 0;
        else left_cover = 1;

        while(max(target, target_L) < l)
        {
            l--;
            left_cost += 2;
            extend(l, r);
        }
    }
}

bool right_cover;
long long right_cost;

void trial_right(int& l, int& r)
{
    right_cost = 0;

    if(r == target_R)
    {
        right_cover = 0;
        right_cost = 0;
    }
    else
    {
        int target = r+1;
        while(target <= target_R && S < L[cycle[target]])
            target++;

        if(target > target_R) right_cover = 0;
        else right_cover = 1;

        while(r < min(target, target_R))
        {
            r++;
            right_cost += 2;
            extend(l, r);
        }
    }
}

long long minimum_walk(vector<int> p, int s)
{
    N = int(p.size());
    S = s;
    P = p;

    target_L = target_R = S;
    for(int i = 0; i < N; i++)
    {
        if(i != P[i])
        {
            target_L = min(target_L, i);
            target_R = max(target_R, i);
        }
    }

    long long basicCost = 0;
    for(int i = 0; i < N; i++)
        basicCost += abs(i - P[i]);

    for(int i = 0; i < N; i++)
    {
        if(cycle[i] != -1) continue;

        curr_cycle++;

        cycle[i] = curr_cycle;
        L[curr_cycle] = R[curr_cycle] = i;

        for(int j = P[i]; j != i; j = P[j])
        {
            cycle[j] = curr_cycle;
            L[curr_cycle] = min(L[curr_cycle], j);
            R[curr_cycle] = max(R[curr_cycle], j);
        }
    }

    long long ans = 0;

    int l = S, r = S;
    while(1)
    {
        extend(l, r);

        if(l == target_L && r == target_R)
            return basicCost + ans;

        int left_l = l;
        int left_r = r;
        trial_left(left_l, left_r);

        int right_l = l;
        int right_r = r;
        trial_right(right_l, right_r);

        if(left_cover)
        {
            assert(right_cover);
            ans += min(left_cost, right_cost);

            assert(left_l == right_l);
            assert(left_r == right_r);

            l = left_l;
            r = left_r;
        }
        else
        {
            assert(!right_cover);
            ans += left_cost + right_cost;
            return basicCost + ans;
        }
    }

    return basicCost + ans;
}

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