oj.uz

Submission #831802

# Submission time Handle Problem Language Result Execution time Memory
831802 2023-08-20T15:23:38 Z finn__ Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 340 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using L = long long;

long long minimum_walk(std::vector<int> p, int s)
{
    int const n = p.size();
    L ans = 0;
    for (int i = 0; i < n; ++i)
        ans += abs(i - p[i]);

    vector<pair<int, int>> cycle(n, {-1, -1});
    for (int i = 0; i < n; ++i)
        if (cycle[i].first == -1)
        {
            int x = i, a = n, b = -1;
            do
            {
                a = min(a, x);
                b = max(b, x);
                x = p[x];
            } while (x != i);
            do
            {
                cycle[x] = {a, b};
                x = p[x];
            } while (x != i);
        }

    set<int> unexplored;
    for (int i = 0; i < n; ++i)
        if (p[i] != i)
            unexplored.insert(i);
    int a = s, b = s;

    auto explore_cycle = [&](int u)
    {
        auto it = unexplored.find(u);
        while (it != unexplored.end())
        {
            a = min(a, u);
            b = max(b, u);
            unexplored.erase(it);
            u = p[u];
            it = unexplored.find(u);
        }
    };

    explore_cycle(s);

    while (!unexplored.empty())
    {
        auto it = unexplored.lower_bound(a);
        if (it != unexplored.end() && *it <= b)
        {
            explore_cycle(*it);
        }
        else
        {
            int cost_left = 0, cost_right = 0, component_end = s;

            int i = a - 1;
            while (i >= 0)
            {
                if (cycle[i].second > s)
                {
                    cost_left += 2;
                    break;
                }
                component_end = min(component_end, min(i, p[i]));
                if (i == component_end)
                    cost_left += 2;
                --i;
            }

            int j = i;

            i = b + 1;
            component_end = s;
            while (i < n)
            {
                if (cycle[i].first < s)
                {
                    cost_right += 2;
                    break;
                }
                component_end = max(component_end, max(i, p[i]));
                if (i == component_end)
                    cost_right += 2;
                ++i;
            }

            if (i == n)
                return ans + cost_left + cost_right;
            if (cost_left < cost_right)
            {
                ans += cost_left;
                a = j;
            }
            else
            {
                ans += cost_right;
                b = i;
            }
        }
    }

    return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 300 KB 3rd lines differ - on the 1st token, expected: '2094', found: '2108'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -