Submission #475604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
475604	2021-09-23T10:02:13 Z	blue	Ancient Books (IOI17_books)	C++17	Compilation error	0 ms	0 KB

books

#include "books.h"
#include <vector>
#include <cassert>
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);

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 == 0)
    {
        left_cover = 0;
        left_cost = 0;
    }
    else
    {
        int target = l-1;
        while(0 <= target && R[cycle[target]] < S)
            target--;

        if(target == -1) left_cover = 0;
        else left_cover = 1;

        while(max(target, 0) < 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 == N-1)
    {
        right_cover = 0;
        right_cost = 0;
    }
    else
    {
        int target = r+1;
        while(target < N && S < L[cycle[target]])
            target++;

        if(target == N) right_cover = 0;
        else right_cover = 1;

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

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

    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 == 0 && r == N-1)
            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;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:104:22: error: 'abs' was not declared in this scope
  104 |         basicCost += abs(i - P[i]);
      |                      ^~~