Submission #1044483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044483		totoro	Ancient Books (IOI17_books)	C++17	50 / 100	292 ms	17096 KiB

books

// SOLVED SUBTASK 1   (12 pts)
// SOLVED SUBTASK 2   (10 pts)
// SOLVED SUBTASK 3   (28 pts)
// UNSOLVED SUBTASK 4 (20 pts)
// UNSOLVED SUBTASK 5 (30 pts)
// [+-+]----------------------
// TOTAL      50/100 pts

#include "books.h"

#include <cmath>

struct Component {
    int start;
    int end;
    Component(int start, int end) : start(start), end(end) {}
};

long long sum_cycles(Component& component, std::vector<int>& p) {
    std::vector<bool> visited(p.size(), false);

    long long sum = 0;
    for (int i = component.start; i <= component.end; ++i) {
        int current = i;
        while (!visited[current]) {
            visited[current] = true;
            long long diff = std::abs(current - p[current]);
            sum += diff;
            current = p[current];
        }
    }

    return sum;
}

long long minimum_walk(std::vector<int> p, int s) {
    bool already_sorted = true;
    size_t first_unsolved = 0;
    for (size_t i = 0; i < p.size(); ++i) {
        if (i != p[i]) {
            already_sorted = false;
            first_unsolved = i;
            break;
        }
    }
    if (already_sorted) {
        return 0;
    }

    size_t last_unsolved = p.size() - 1;
    for (int i = p.size() - 1; i >= 0; --i) {
        if (i != p[i]) {
            last_unsolved = i;
            break;
        }
    }

    std::vector<Component> components;

    int block_start = 0;
    int block_end = 0;
    bool in_block = false;
    size_t distances = 0;
    for (size_t i = first_unsolved; i <= last_unsolved; ++i) {
        if (i == p[i] && !in_block) {
            ++distances;
            continue;
        }
        if (!in_block) {
            block_start = i;
            block_end = p[i];
            in_block = true;
        } else {
            block_end = std::max(block_end, p[i]);
        }
        if (i == block_end) {
            components.emplace_back(block_start, block_end);
            in_block = false;
        }
    }

    size_t final_distances = 2 * (distances + components.size() - 1);
    if (s < first_unsolved) {
        final_distances += 2 * (first_unsolved - s);
    } else if (s > last_unsolved) {
        final_distances += 2 * (s - last_unsolved);
    }

    size_t sum = final_distances;
    for (auto& component : components) {
        sum += sum_cycles(component, p);
    }

    return sum;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:40:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   40 |         if (i != p[i]) {
books.cpp:65:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   65 |         if (i == p[i] && !in_block) {
books.cpp:76:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |         if (i == block_end) {
      |             ~~^~~~~~~~~~~~
books.cpp:83:11: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     if (s < first_unsolved) {
      |         ~~^~~~~~~~~~~~~~~~
books.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     } else if (s > last_unsolved) {
      |                ~~^~~~~~~~~~~~~~~

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