Submission #638780

#	Time	Username	Problem	Language	Result	Execution time	Memory
638780		qwerasdfzxcl	Ancient Books (IOI17_books)	C++17	50 / 100	127 ms	60236 KiB

books

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

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

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

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

    int mn = s;
    int mx = s;

    int ptl = s, ptr = s;

    while(mn <= ptl || ptr <= mx){
        int j = -1;

        if (mn <= ptl){
            if (visited[ptl]) {--ptl; continue;}
            j = ptl--;
        }
        else{
            if (visited[ptr]) {++ptr; continue;}
            j = ptr++;
        }

        for (;!visited[j];j=a[j]){
            visited[j] = 1;
            ret += myabs(j-a[j]);
            mn = min(mn, j);
            mx = max(mx, j);
        }
    }

    ll ret2 = solve(mx+1, r, mx+1);
    ll ret3 = solve(l, mn-1, mn-1);
    return ret + (ret2 ? ret2+2 : 0) + (ret3 ? ret3+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;

	return solve(1, n, S+1);
}

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