Submission #1351890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351890		Andrey	Ancient Books (IOI17_books)	C++17	50 / 100	86 ms	19940 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;

long long minimum_walk(std::vector<int> p, int s) {
    int n = p.size();
    long long ans = 0;
    int l = s,r = s;
    vector<int> col(n,-1);
    vector<int> fl(n,-1);
    vector<int> fr(n,n+1);
    for(int i = 0; i < n; i++) {
        ans+=abs(p[i]-i);
    }
    for(int i = 0; i < s; i++) {
        if(p[i] != i) {
            l = i;
            break;
        }
    }
    for(int i = n-1; i > s; i--) {
        if(p[i] != i) {
            r = i;
            break;
        }
    }
    for(int i = 0; i < n; i++) {
        int y = i;
        while(col[y] == -1) {
            col[y] = i;
            if(y <= s) {
                fl[i] = max(fl[i],y);
            }
            if(y >= s) {
                fr[i] = min(fr[i],y);
            }
            y = p[y];
        }
    }
    int z = 0;
    while(l < r) {
        int a = 1,b = 1;
        if(z == 0) {
            a = 0;
            b = 0;
        }
        int l1 = l,x = -1;
        for(int i = l; i < s; i++) {
            int c = col[i];
            if(fr[c] != n+1) {
                break;
            }
            x = max(x,fl[c]);
            if(x <= i) {
                a++;
                l1 = i+1;
            }
        }
        int r1 = r;
        x = n+1;
        for(int i = r; i > s; i--) {
            int c = col[i];
            if(fl[c] != -1) {
                break;
            }
            x = min(x,fr[c]);
            if(x >= i) {
                b++;
                r1 = i-1;
            }
        }
        if(z == 0) {
            ans+=2*(a+b);
        }
        else {
            ans+=2*min(a,b);
        }
        l = l1;
        r = r1;
        l1 = max(l1,max(fl[col[l]],fl[col[r]]));
        r1 = min(r1,min(fr[col[l]],fr[col[r]]));
        while(l1 > l || r1 < r) {
            if(l1 > l) {
                l++;
            }
            else {
                r--;
            }
            l1 = max(l1,max(fl[col[l]],fl[col[r]]));
            r1 = min(r1,min(fr[col[l]],fr[col[r]]));
        }
        l++;
        r--;
        z++;
    }
    return ans;
}

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