제출 #46905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46905		SpaimaCarpatilor	고대 책들 (IOI17_books)	C++17	42 / 100	2062 ms	32256 KiB

books

#include "books.h"
#include<bits/stdc++.h>

using namespace std;

int N, S, p[1000009], prv[1000009], nxt[1000009], dp[1009][1009];
bool ap[1000009];
pair < int, int > jump[1009][1009];

void update (int &x, int y)
{
    if (y < x) x = y;
}

long long minimum_walk (vector < int > pp, int ss)
{
    N = pp.size (), S = ss + 1;
    for (int i=1; i<=N; i++)
        p[i] = pp[i - 1] + 1;
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            int j = p[i], maxRight = i;
            ap[i] = 1;
            while (j != i)
                ap[j] = 1, maxRight = max (maxRight, j), j = p[j];
            nxt[i] = maxRight, prv[i] = i, j = p[i];
            while (j != i)
                nxt[j] = maxRight, prv[j] = i, j = p[j];
        }
    long long ans = 0;
    for (int i=1; i<=N; i++)
    {
        int curr = i - p[i];
        if (curr < 0) curr = -curr;
        ans += curr;
    }
    int targetL = N + 1, targetR = 0;
    for (int i=1; i<=N; i++)
        if (p[i] != i)
        {
            if (targetL == N + 1)
                targetL = i;
            targetR = i;
        }
    if (targetR == 0) return ans;
    targetR = max (targetR, S);
    targetL = min (targetL, S);
    for (int i=1; i<=N; i++)
    {
        jump[i][i] = {prv[i], nxt[i]};
        for (int j=i + 1; j<=N; j++)
            jump[i][j].first = min (jump[i][j - 1].first, prv[j]),
            jump[i][j].second = max (jump[i][j - 1].second, nxt[j]);
    }
    for (int i=1; i<=N; i++)
        for (int j=N; j>=i; j--)
            if (jump[i][j].first != i || jump[i][j].second != j)
                jump[i][j] = jump[jump[i][j].first][jump[i][j].second];
    for (int i=1; i<=N; i++)
        for (int j=i; j<=N; j++)
            dp[i][j] = 3 * N + 10;
    dp[S][S] = 0;
    for (int i=S; i>=targetL; i--)
        for (int j=S; j<=targetR; j++)
        {
            if (jump[i][j].first != i || jump[i][j].second != j)
            {
                update (dp[jump[i][j].first][jump[i][j].second], dp[i][j]);
                continue;
            }
            if (j < N)
                update (dp[i][j + 1], dp[i][j] + 1);
            if (i > 1)
                update (dp[i - 1][j], dp[i][j] + 1);
        }
    return ans + 2LL * dp[targetL][targetR];
}

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