Submission #1268007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268007		LaMatematica14	Ancient Books (IOI17_books)	C++20	0 / 100	0 ms	328 KiB

books

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

long long minimum_walk(vector<int> p, int s) {
    long long ans = 0, N = p.size();
    for (int i=0; i<N; i++) ans += abs(p[i]-i);
    int last_ordered = N, first_unordered = -1;
    for (int i = 0; i < s; i++) {
        if (p[i] != i) break;
        first_unordered = i;
    }
    for (int i = N-1; i > s; i--) {
        if (p[i] != i) break;
        last_ordered = i;
    }
    if (last_ordered == 0) return 0;

    auto expand = [&](int start, int l, int r) -> pair<int, int> {
        int m_l = l, m_r = r;
        m_l = min(start, m_l); m_r = max(start, m_r);
		//cout << "start expand " << start << " " << l << " " << r << endl;
        while (m_l != l || m_r != r) {
			//cout << "curr max " << m_l << " " << m_r << endl;
            for (; r <= m_r; r++) {
                m_r = max(m_r, p[r]);
                m_l = min(m_l, p[r]);
            }
			r--;
            for (; l >= m_l; l--) {
                m_r = max(m_r, p[l]);
                m_l = min(m_l, p[l]);
            }
			l++;
			//cout << "expanded " << l << " " << r << endl;
        }
        return {l, r};
    };

    int curr_seg_left = s, curr_seg_right = s;
    tie(curr_seg_left, curr_seg_left) = expand(s, s, s); 
    while (1) {
		//cout << "working with " << curr_seg_left << " " << curr_seg_right << endl;
        int ns_left = 0, ns_right = 0;
        int superseg_left = -1, superseg_right = -1;
        // count segments to the left
        while (curr_seg_left > first_unordered+1) {
			//cout << "expanding left" << endl;
            auto [new_left, new_right] = expand(curr_seg_left-1, curr_seg_left, curr_seg_right);
            if (new_right > curr_seg_right) {
                // found superseg
                superseg_left = new_left;
                superseg_right = new_right;
                //...
                break;
            }
            else {
                ns_left++;
                curr_seg_left = new_left;
            }
        }
         
        // count segments to the right
        while (curr_seg_right < last_ordered-1) {
			//cout << "expanding right" << endl;
            auto [new_left, new_right] = expand(curr_seg_right+1, curr_seg_left, curr_seg_right);
            if (new_left < curr_seg_left) {
                // found superseg
                assert(superseg_left == new_left);
                assert(superseg_right == new_right);
                // ...
                break;
            }
            else {
                ns_right++;
                curr_seg_right = new_right;
            }
        }

        // check minim or exit
		//cout << "segments found " << ns_left << " " << ns_right << endl;
        if (superseg_left != -1) {
            //assert(superseg_right != curr_seg_right);
            ans += min(ns_left, ns_right)+1;
            curr_seg_left = superseg_left;
            curr_seg_right = superseg_right;
        }
        else {
            ans += (ns_left+ns_right)*2;
            return ans;
        }
    }
    return ans;
}

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