Submission #206624

#	Time	Username	Problem	Language	Result	Execution time	Memory
206624		anonymous	Ancient Books (IOI17_books)	C++14	50 / 100	2083 ms	27768 KiB

books

#include "books.h"
#include<iostream>
#define MAXN 1000005
#define LL long long
using namespace std;
int N, S, cyc = 1, eL=N+1, eR=0, Lcur, Rcur;
int L[MAXN], R[MAXN], P[MAXN], C[MAXN];
bool vis[MAXN];
LL ans;
LL minimum_walk(vector<int> p, int s) {
	N = p.size(), S = s+1, Lcur = S, Rcur = S;
	for (int i=0; i<N; i++) {
        P[i+1]=p[i]+1; //1 index
        ans += (LL) max(p[i] - i, i - p[i]);
	}
	for (int i=1; i<=N; i++) {
        int cur = P[i];
        L[cyc] = 1<<30, R[cyc] = -1<<30;
        while (!vis[cur]) {
            L[cyc] = min(L[cyc], cur);
            R[cyc] = max(R[cyc], cur);
            vis[cur] = true;
            cur = P[cur];
        }
        cyc++;
	}
	for (int i=1; i<=N; i++) {
        if (P[i] != i) {
            eL = i;
            break;
        }
	}
	for (int i=N; i>=1; i--) {
        if (P[i] != i) {
            eR = i;
            break;
        }
	}
	while (Lcur > eL || Rcur < eR) {
        //expand left and right as much as frontier
        //printf("%d %d %d %d\n",Lcur, Rcur, eL, eR);
        int pt1 = Lcur, pt2 = Rcur;
        while (pt1 >= Lcur || pt2 <= Rcur) {
            if (pt1 >= Lcur) {
                Lcur = min(Lcur, L[pt1]);
                Rcur = max(Rcur, R[pt1]);
                pt1--;
            }
            if (pt2 <= Rcur) {
                Lcur = min(Lcur, L[pt2]);
                Rcur = max(Rcur, R[pt2]);
                pt2++;
            }
        }
        //if one boundary is reached
        if (Lcur <= eL && Rcur >= eR) {
            break;
        } else if (Lcur <= eL) {
            ans+=2;
            Rcur++;
        } else if (Rcur >= eR) {
            ans+=2;
            Lcur--;
        }
        //test expand right Cost to go beyond
	}
	return(ans);
}

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