Submission #1061903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061903		_8_8_	Ancient Books (IOI17_books)	C++17	100 / 100	112 ms	14968 KiB

books

    #include "books.h"
    #include <bits/stdc++.h>
        
    using namespace std;
    typedef long long ll;
    const int N = 1e6 + 12;
    int n;
     
    long long minimum_walk(vector<int> p, int s) {
        n = (int)p.size();
        int it = 0;
        ll res = 0;
        for(int i = 0;i < n;i++) {
            res += abs(i - p[i]);
        }
        if(s == 0) {
            int nn = -1;
            for(int i = n - 1;i >= 0;i--) {
                if(p[i] != i) {
                    nn = i;
                    break;
                }
            }
            int mx = -1;
            for(int i = 0;i < nn;i++) {
                mx = max(mx,p[i]);
                if(mx == i) {
                    res += 2;
                }
            }
            return res;
        }
        int l = s,r = s,R = s,L = s;
        int tl,tr;
        for(int i = 0;i < n;i++) {
            if(p[i] != i) {
                tl = i;
                break;
            }
        }
        for(int i = n - 1;i >= 0;i--) {
            if(i != p[i]) {
                tr = i;
                break;
            }
        }
        if(!res) {
            return res;
        }
        while(true) {
            R = max({R,p[r],p[l]});
            L = min({L,p[l],p[r]});
            if(l <= tl && r >= tr) {
                break;
            }
            if(r < R) {
                assert(R <= tr);
                r++;
            } else if(L < l) {
                assert(L >= tl);
                l--;
            } else {
                int l_ = -1e9,r_ = (int)1e9;
                for(int i = l - 1;i >= tl;i--) {
                    if(p[i] > r) {
                        l_ = i;
                        break;
                    }
                }
                for(int i = r + 1;i <= tr;i++) {
                    if(p[i] < l) {
                        r_ = i;
                        break;
                    }
                }
                if(l_ == (int)-1e9) {
                    assert(r_ == (int)1e9);
                    if(l > tl) {
                        res += 2;
                        l--;
                        int mn = (int)1e9;
                        for(int j = l;j > tl;--j) {
                            assert(p[j] <= l && p[j] >= tl);
                            mn = min(mn,p[j]);
                            if(j == mn) {
                                res += 2;
                            }
                        }
                    }
                    if(r < tr) {
                        res += 2;
                        r++;
                        int mx = -1;
                        for(int j = r;j < tr;j++) {
                            assert(p[j] >= r && p[j] <= tr);
                            mx = max(mx,p[j]);
                            if(mx == j) {
                                res += 2;
                            }
                        }
                    }
                    return res;
                } else {
                    ll a = 2,b = 2;
                    int mn = (int)1e9;
                    for(int j = l - 1;j > l_;j--) {
                        mn = min(mn,p[j]);
                        if(mn == j) {
                            a += 2;
                        }
                    }
                    int mx= -1;
                    for(int j = r + 1;j < r_;j++) {
                        mx = max(mx,p[j]);
                        if(mx == j) b += 2;
                    }
                    if(a < b) {
                        res += a;
                        for(int j = l - 1;j > l_;j--) {
                            L = min(L,p[j]);
                            R = max(R,p[j]);
                        }
                        l = l_;
                    } else {
                        res += b;
                        for(int j = r + 1;j < r_;j++) {
                            L = min(L,p[j]);
                            R = max(R,p[j]);
                        }
                        r = r_;
                    }
                }
            }
        }
        return res;
    }

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:11:13: warning: unused variable 'it' [-Wunused-variable]
   11 |         int it = 0;
      |             ^~

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