Submission #638777

#	Time	Username	Problem	Language	Result	Execution time	Memory
638777		qwerasdfzxcl	Ancient Books (IOI17_books)	C++17	50 / 100	122 ms	35304 KiB

books

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

using namespace std;
typedef long long ll;
int a[1001000], n, s;
bool visited[1001000];

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}

ll solve(int l, int r){
    if (l>r) return 0;
    ll ret = 0;
    int mx = l;

    for (int i=l;i<=mx;i++) if (!visited[i]){
        for (int j=i;!visited[j];j=a[j]){
            visited[j] = 1;
            ret += myabs(j - a[j]);
            mx = max(mx, j);
        }
    }

    ll ret2 = solve(mx+1, r);
    return ret + (ret2 ? ret2+2 : 0);
}

long long minimum_walk(std::vector<int> P, int S) {
    n = P.size();
	for (int i=1;i<=n;i++) a[i] = P[i-1] + 1;
	s = S+1;

	return solve(1, n);
}

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