Submission #959761

#	Time	Username	Problem	Language	Result	Execution time	Memory
959761		12345678	Ancient Books (IOI17_books)	C++17	50 / 100	81 ms	16224 KiB

books

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

using namespace std;

#define ll long long

const int nx=1e6+5;

int vs[nx], n, lst, dp[nx];
ll res;

long long minimum_walk(std::vector<int> p, int s) {
    n=p.size();
    for (int i=0; i<n; i++)
    {
        res+=abs(i-p[i]);
        dp[min(i, p[i])]++;
        dp[max(i, p[i])]--;
    }
    for (int i=1; i<n; i++) dp[i]+=dp[i-1];
    for (int i=n-1; i>=s; i--)
    {
        if (dp[i]) break;
        dp[i]=1;
    }
    for (int i=0; i<s; i++)
    {
        if (dp[i]) break;
        dp[i]=1;
    }
    for (int i=0; i<n-1; i++) if (dp[i]==0) res+=2;
	return res;
}

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