Submission #290444

#	Time	Username	Problem	Language	Result	Execution time	Memory
290444		A02	Ancient Books (IOI17_books)	C++14	100 / 100	163 ms	19200 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

long long minimum_walk(vector<int> p, int s) {

    vector<int> np;
    long long book_total = 0;

    int left_start = p.size();
    int right_start = 0;
    for (int i = 0; i < p.size(); i++){
        if (p[i] != i){
            left_start = min(left_start, i);
        }
    }
    for (int i = p.size() - 1; i >= 0; i--){
        if (p[i] != i){
            right_start = max(right_start, i);
        }
    }



    if (left_start == p.size()){
        return 0;
    }

    if (s < left_start){
        s = 0;
        book_total += 2 * (left_start - s);
    } else {
        s -= left_start;
    }

    right_start -= left_start;

    if (s > right_start){
        s = right_start;
        book_total += 2 * (s - (right_start));

    }

    for (int i = left_start; i <= right_start + left_start; i++){
        np.push_back(p[i] - left_start);
        //cout << np[i - left_start] << 'a' << endl;
    }

    p = np;

	int n = p.size();

	for (int i = 0; i < n; i++){
        book_total += max(p[i] - i, i - p[i]);
	}

//	if (s == 0){
//        int current_region_max = 0;
//        int prev_visited = 0;
//        for (int i = 0; i < n; i++){
//            if (current_region_max < i && p[i] != i){
//                book_total += 2 * (i - current_region_max);
//            }
//            if (p[i] != i){
//                current_region_max = max(current_region_max, i);
//                current_region_max = max(current_region_max, p[i]);
//            }
//        }
//	}

    int left_frontier = s;
    int right_frontier = s;
    long long left_cost = 0;
    long long right_cost = 0;

    bool is_joined = true;

    int v_l_frontier = s;
    int v_r_frontier = s;

    if (p[s] < s){
        left_frontier = p[s];
    }
    if (p[s] > s){
        right_frontier = p[s];
    }
    //cout << left_frontier << ' ' << right_frontier << endl;
    while(left_frontier < v_l_frontier || right_frontier > v_r_frontier){
        if (right_frontier > v_r_frontier){

            for (int i = v_r_frontier + 1; i <= right_frontier; i++){
                v_r_frontier++;
                if (p[i] > right_frontier){
                    right_frontier = p[i];
                }
                if (p[i] < left_frontier){
                    left_frontier = p[i];
                }
            }
        }

        if (left_frontier < v_l_frontier){
            for (int i = v_l_frontier - 1; i >= left_frontier; i--){
                v_l_frontier--;
                if (p[i] > right_frontier){
                    right_frontier = p[i];
                }
                if (p[i] < left_frontier){
                    left_frontier = p[i];
                }
            }

        }
    }


    while (left_frontier > 0 || right_frontier < n - 1){
        //cout << left_frontier << 'x' << right_frontier << endl;
        is_joined = false;

        if (right_frontier < n - 1){
            int original_left_frontier = left_frontier;
            right_frontier++;
            right_cost++;

            int left_visited_frontier = left_frontier;
            int right_visited_frontier = right_frontier - 1;
            //cout << left_frontier << 'r' << right_frontier << endl;
            while(left_frontier < left_visited_frontier || right_frontier > right_visited_frontier){
                //cout << left_frontier << 's' << right_frontier << endl;
                if (right_frontier > right_visited_frontier){

                    for (int i = right_visited_frontier + 1; i <= right_frontier; i++){
                        right_visited_frontier++;
                        if (p[i] > right_frontier){
                            right_frontier = p[i];
                        }
                        if (p[i] < left_frontier){
                            left_frontier = p[i];
                        }
                    }
                }

                if (left_frontier < left_visited_frontier){
                    for (int i = left_visited_frontier - 1; i >= left_frontier; i--){
                        left_visited_frontier--;
                        if (p[i] > right_frontier){
                            right_frontier = p[i];
                        }
                        if (p[i] < left_frontier){
                            left_frontier = p[i];
                        }
                    }

                }
            }

            if (original_left_frontier != left_frontier){
                is_joined = true;
            }
        }
        //cout << 'a' << endl;
        if (!is_joined && left_frontier > 0){

            int original_right_frontier = right_frontier;
            left_frontier--;
            left_cost++;

            int left_visited_frontier = left_frontier + 1;
            int right_visited_frontier = right_frontier;
            //cout << 'c' << endl;
            while(left_frontier < left_visited_frontier || right_frontier > right_visited_frontier){
                //cout << left_frontier << 'f' << right_frontier << endl;
                //cout << left_visited_frontier << ' ' << right_visited_frontier << endl;
                if (right_frontier > right_visited_frontier){
                    //right_visited_frontier++;
                    for (int i = right_visited_frontier + 1; i <= right_frontier; i++){
                        right_visited_frontier++;
                        if (p[i] > right_frontier){
                            right_frontier = p[i];
                        }
                        if (p[i] < left_frontier){
                            left_frontier = p[i];
                        }
                    }
                }

                if (left_frontier < left_visited_frontier){
                    for (int i = left_visited_frontier - 1; i >= left_frontier; i--){
                        left_visited_frontier--;
                        if (p[i] > right_frontier){
                            right_frontier = p[i];
                        }
                        if (p[i] < left_frontier){
                            left_frontier = p[i];
                        }
                    }

                }
            }

            if (original_right_frontier != right_frontier){
                is_joined = true;
            }

        }
        //cout << 'b' << endl;
        if (is_joined){
            book_total += 2 * right_cost;
            left_cost = 0;
            right_cost = 0;
        }

    }

    book_total += 2 * (left_cost + right_cost);

	return book_total;

}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < p.size(); i++){
      |                     ~~^~~~~~~~~~
books.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if (left_start == p.size()){
      |         ~~~~~~~~~~~^~~~~~~~~~~

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