oj.uz

Submission #475606

# Submission time Handle Problem Language Result Execution time Memory
475606 2021-09-23T10:08:20 Z blue Ancient Books (IOI17_books) C++17
100 / 100
 194 ms 30652 KB 
#include "books.h"
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;

const int maxN = 1'000'000;

int N;
int S;
vector<int> P;

int curr_cycle = -1;
vector<int> cycle(maxN, -1);
vector<int> L(maxN, 1+maxN);
vector<int> R(maxN, -1);

int target_L, target_R;

void extend(int& l, int& r) //all extensions in [l+1, r-1] have already been done
{
    int new_l = l;
    int new_r = r;

    while(1)
    {
        new_l = min(new_l, min(L[cycle[l]], L[cycle[r]]));
        new_r = max(new_r, max(R[cycle[l]], R[cycle[r]]));

        if(new_l < l)
            l--;
        else if(r < new_r)
            r++;
        else
            break;
    }
}

bool left_cover;
long long left_cost;

void trial_left(int& l, int& r) //l, r is fully extended,    extend it further
{
    left_cost = 0;

    if(l == target_L)
    {
        left_cover = 0;
        left_cost = 0;
    }
    else
    {
        int target = l-1;
        while(target_L <= target && R[cycle[target]] < S)
            target--;

        if(target < target_L) left_cover = 0;
        else left_cover = 1;

        while(max(target, target_L) < l)
        {
            l--;
            left_cost += 2;
            extend(l, r);
        }
    }
}

bool right_cover;
long long right_cost;

void trial_right(int& l, int& r)
{
    right_cost = 0;

    if(r == target_R)
    {
        right_cover = 0;
        right_cost = 0;
    }
    else
    {
        int target = r+1;
        while(target <= target_R && S < L[cycle[target]])
            target++;

        if(target > target_R) right_cover = 0;
        else right_cover = 1;

        while(r < min(target, target_R))
        {
            r++;
            right_cost += 2;
            extend(l, r);
        }
    }
}

long long minimum_walk(vector<int> p, int s)
{
    N = int(p.size());
    S = s;
    P = p;

    target_L = target_R = S;
    for(int i = 0; i < N; i++)
    {
        if(i != P[i])
        {
            target_L = min(target_L, i);
            target_R = max(target_R, i);
        }
    }

    long long basicCost = 0;
    for(int i = 0; i < N; i++)
        basicCost += abs(i - P[i]);

    for(int i = 0; i < N; i++)
    {
        if(cycle[i] != -1) continue;

        curr_cycle++;

        cycle[i] = curr_cycle;
        L[curr_cycle] = R[curr_cycle] = i;

        for(int j = P[i]; j != i; j = P[j])
        {
            cycle[j] = curr_cycle;
            L[curr_cycle] = min(L[curr_cycle], j);
            R[curr_cycle] = max(R[curr_cycle], j);
        }
    }

    long long ans = 0;

    int l = S, r = S;
    while(1)
    {
        extend(l, r);

        if(l == target_L && r == target_R)
            return basicCost + ans;

        int left_l = l;
        int left_r = r;
        trial_left(left_l, left_r);

        int right_l = l;
        int right_r = r;
        trial_right(right_l, right_r);

        if(left_cover)
        {
            assert(right_cover);
            ans += min(left_cost, right_cost);

            assert(left_l == right_l);
            assert(left_r == right_r);

            l = left_l;
            r = left_r;
        }
        else
        {
            assert(!right_cover);
            ans += left_cost + right_cost;
            return basicCost + ans;
        }
    }

    return basicCost + ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 11952 KB Output is correct
7 Correct 6 ms 12036 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 6 ms 11920 KB Output is correct
11 Correct 6 ms 12048 KB Output is correct
12 Correct 6 ms 11980 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12028 KB Output is correct
17 Correct 6 ms 11984 KB Output is correct
18 Correct 5 ms 12032 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 11952 KB Output is correct
7 Correct 6 ms 12036 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 6 ms 11920 KB Output is correct
11 Correct 6 ms 12048 KB Output is correct
12 Correct 6 ms 11980 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12028 KB Output is correct
17 Correct 6 ms 11984 KB Output is correct
18 Correct 5 ms 12032 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 8 ms 11980 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 7 ms 11980 KB Output is correct
23 Correct 7 ms 11940 KB Output is correct
24 Correct 6 ms 11980 KB Output is correct
25 Correct 6 ms 11980 KB Output is correct
26 Correct 7 ms 11972 KB Output is correct
27 Correct 6 ms 12032 KB Output is correct
28 Correct 7 ms 11980 KB Output is correct
29 Correct 6 ms 11996 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 11952 KB Output is correct
7 Correct 6 ms 12036 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 6 ms 11920 KB Output is correct
11 Correct 6 ms 12048 KB Output is correct
12 Correct 6 ms 11980 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12028 KB Output is correct
17 Correct 6 ms 11984 KB Output is correct
18 Correct 5 ms 12032 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 8 ms 11980 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 7 ms 11980 KB Output is correct
23 Correct 7 ms 11940 KB Output is correct
24 Correct 6 ms 11980 KB Output is correct
25 Correct 6 ms 11980 KB Output is correct
26 Correct 7 ms 11972 KB Output is correct
27 Correct 6 ms 12032 KB Output is correct
28 Correct 7 ms 11980 KB Output is correct
29 Correct 6 ms 11996 KB Output is correct
30 Correct 194 ms 30420 KB Output is correct
31 Correct 191 ms 30396 KB Output is correct
32 Correct 138 ms 30404 KB Output is correct
33 Correct 151 ms 30480 KB Output is correct
34 Correct 153 ms 30404 KB Output is correct
35 Correct 174 ms 30388 KB Output is correct
36 Correct 162 ms 30500 KB Output is correct
37 Correct 139 ms 30392 KB Output is correct
38 Correct 143 ms 30504 KB Output is correct
39 Correct 192 ms 30400 KB Output is correct
40 Correct 141 ms 30380 KB Output is correct
41 Correct 161 ms 30388 KB Output is correct
42 Correct 180 ms 30524 KB Output is correct
43 Correct 153 ms 30392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11956 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 12036 KB Output is correct
6 Correct 8 ms 11980 KB Output is correct
7 Correct 6 ms 12012 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 6 ms 11980 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 8 ms 11960 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 8 ms 11940 KB Output is correct
16 Correct 6 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 5 ms 11980 KB Output is correct
19 Correct 6 ms 12008 KB Output is correct
20 Correct 6 ms 12004 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 11952 KB Output is correct
7 Correct 6 ms 12036 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 11980 KB Output is correct
10 Correct 6 ms 11920 KB Output is correct
11 Correct 6 ms 12048 KB Output is correct
12 Correct 6 ms 11980 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12028 KB Output is correct
17 Correct 6 ms 11984 KB Output is correct
18 Correct 5 ms 12032 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 8 ms 11980 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 7 ms 11980 KB Output is correct
23 Correct 7 ms 11940 KB Output is correct
24 Correct 6 ms 11980 KB Output is correct
25 Correct 6 ms 11980 KB Output is correct
26 Correct 7 ms 11972 KB Output is correct
27 Correct 6 ms 12032 KB Output is correct
28 Correct 7 ms 11980 KB Output is correct
29 Correct 6 ms 11996 KB Output is correct
30 Correct 194 ms 30420 KB Output is correct
31 Correct 191 ms 30396 KB Output is correct
32 Correct 138 ms 30404 KB Output is correct
33 Correct 151 ms 30480 KB Output is correct
34 Correct 153 ms 30404 KB Output is correct
35 Correct 174 ms 30388 KB Output is correct
36 Correct 162 ms 30500 KB Output is correct
37 Correct 139 ms 30392 KB Output is correct
38 Correct 143 ms 30504 KB Output is correct
39 Correct 192 ms 30400 KB Output is correct
40 Correct 141 ms 30380 KB Output is correct
41 Correct 161 ms 30388 KB Output is correct
42 Correct 180 ms 30524 KB Output is correct
43 Correct 153 ms 30392 KB Output is correct
44 Correct 7 ms 11956 KB Output is correct
45 Correct 6 ms 11980 KB Output is correct
46 Correct 6 ms 11980 KB Output is correct
47 Correct 6 ms 11980 KB Output is correct
48 Correct 6 ms 12036 KB Output is correct
49 Correct 8 ms 11980 KB Output is correct
50 Correct 6 ms 12012 KB Output is correct
51 Correct 6 ms 11980 KB Output is correct
52 Correct 7 ms 11980 KB Output is correct
53 Correct 6 ms 11980 KB Output is correct
54 Correct 6 ms 11980 KB Output is correct
55 Correct 8 ms 11960 KB Output is correct
56 Correct 6 ms 11980 KB Output is correct
57 Correct 6 ms 11980 KB Output is correct
58 Correct 8 ms 11940 KB Output is correct
59 Correct 6 ms 11980 KB Output is correct
60 Correct 6 ms 11980 KB Output is correct
61 Correct 5 ms 11980 KB Output is correct
62 Correct 6 ms 12008 KB Output is correct
63 Correct 6 ms 12004 KB Output is correct
64 Correct 145 ms 30396 KB Output is correct
65 Correct 190 ms 30404 KB Output is correct
66 Correct 184 ms 30404 KB Output is correct
67 Correct 144 ms 30424 KB Output is correct
68 Correct 20 ms 13772 KB Output is correct
69 Correct 19 ms 13692 KB Output is correct
70 Correct 20 ms 13716 KB Output is correct
71 Correct 21 ms 13752 KB Output is correct
72 Correct 27 ms 13692 KB Output is correct
73 Correct 27 ms 13772 KB Output is correct
74 Correct 164 ms 30380 KB Output is correct
75 Correct 153 ms 30388 KB Output is correct
76 Correct 154 ms 30404 KB Output is correct
77 Correct 150 ms 30384 KB Output is correct
78 Correct 152 ms 30388 KB Output is correct
79 Correct 145 ms 30396 KB Output is correct
80 Correct 134 ms 30396 KB Output is correct
81 Correct 144 ms 30404 KB Output is correct
82 Correct 144 ms 30396 KB Output is correct
83 Correct 147 ms 30404 KB Output is correct
84 Correct 152 ms 30508 KB Output is correct
85 Correct 148 ms 30640 KB Output is correct
86 Correct 149 ms 30396 KB Output is correct
87 Correct 149 ms 30404 KB Output is correct
88 Correct 153 ms 30500 KB Output is correct
89 Correct 159 ms 30652 KB Output is correct
90 Correct 153 ms 30504 KB Output is correct
91 Correct 158 ms 30384 KB Output is correct
92 Correct 149 ms 30428 KB Output is correct