oj.uz

Submission #290434

# Submission time Handle Problem Language Result Execution time Memory
290434 2020-09-03T19:32:13 Z A02 Ancient Books (IOI17_books) C++14
20 / 100
 1 ms 384 KB 
#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; i++){
        np.push_back(p[i]);
    }

    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;

            while(left_frontier < left_visited_frontier || right_frontier > right_visited_frontier){

                if (right_frontier > right_visited_frontier){
                    right_visited_frontier++;
                    for (int i = right_visited_frontier + 1; i <= right_frontier; i++){
                        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

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:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (left_start == p.size()){
      |         ~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 30.0

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