Submission #759478

#	Time	Username	Problem	Language	Result	Execution time	Memory
759478		boris_mihov	Ancient Books (IOI17_books)	C++17	50 / 100	102 ms	23860 KiB

books

#include "books.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int n, s;
int p[MAXN];
int add[MAXN];
bool vis[MAXN];

llong minimum_walk(std::vector <int> P, int S) 
{
    llong ans = 0;
    n = P.size(); s = S + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        p[i] = P[i - 1] + 1;
        ans += abs(i - p[i]);
    }

    int max = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (vis[i] || i == p[i])
        {
            continue;
        }

        int curr = i;
        int currMax = i;
        while (!vis[curr])
        {
            vis[curr] = true;
            currMax = std::max(currMax, curr);
            curr = p[curr];
        }

        add[i]++;
        add[currMax]--;
        max = std::max(max, currMax);
    }

    int balance = 0;
    for (int i = 1 ; i < max ; ++i)
    {
        balance += add[i];
        if (balance == 0)
        {
            ans += 2;
        }
    }

	return ans;
}

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