Submission #206634

#	Time	Username	Problem	Language	Result	Execution time	Memory
206634		anonymous	Ancient Books (IOI17_books)	C++14	50 / 100	265 ms	24952 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);
            C[cur] = cyc;
            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 allows
        //printf("%d %d %d %d\n",Lcur, Rcur, eL, eR);
        int pt1 = Lcur, pt2 = Rcur; //[Lcur, Rcur] can be reached
        while (pt1 >= Lcur || pt2 <= Rcur) {
            if (pt1 >= Lcur) {
                Lcur = min(Lcur, L[C[pt1]]);
                Rcur = max(Rcur, R[C[pt1]]);
                pt1--;
            }
            if (pt2 <= Rcur) {
                Lcur = min(Lcur, L[C[pt2]]);
                Rcur = max(Rcur, R[C[pt2]]);
                pt2++;
            }
        }
        //if one boundary is reached
        //printf("After: %d %d\n",Lcur, Rcur);
        if (Lcur <= eL && Rcur >= eR) {
            break;
        } else if (Lcur <= eL) {
            ans+=2;
            Rcur++;
        } else if (Rcur >= eR) {
            ans+=2;
            Lcur--;
        } else {
            //test expand right Cost to go beyond
            int tmpL = Lcur, tmpR = Rcur, ptL = Lcur, ptR = Rcur;
            int Lcost = 0, Rcost = 0;
            bool root = true;
            //check R cost:
            while (ptR < eR) {
                if (ptR > tmpR) {tmpR = ptR, Rcost++;}
                tmpR = max(tmpR, R[C[ptR]]);
                if (L[C[ptR]] < Lcur) {
                    root = false;
                    break;
                }
                ptR++;
            }
            //check L cost:
            while (ptL > eL) {
                if (ptL < tmpL) {tmpL = ptL, Lcost++;}
                tmpL = min(tmpL, L[C[ptL]]);
                if (R[C[ptL]] > Rcur) {
                    root = false;
                    break;
                }
                ptL--;
            }
            if (root) {
                ans+=2*(Lcost + Rcost);
                break;
            } else if (Lcost > Rcost) {
                Rcur = ptR, Lcur = L[C[ptR]];
                ans+=2*Rcost;
            } else {
                Lcur = ptL, Rcur = R[C[ptL]];
                ans+=2*Lcost;
            }
        }
	}
	return(ans);
}

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