| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 290432 | 2020-09-03T19:24:50 Z | A02 | Ancient Books (IOI17_books) | C++14 | 2000 ms | 256 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];
}
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];
}
}
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){
//cout << left_frontier << ' ' << right_frontier << endl;
is_joined = false;
if (right_frontier < n){
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];
}
}
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];
}
}
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;
}
}
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
| # | 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 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 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 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 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 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2084 ms | 256 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 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 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 | Halted | 0 ms | 0 KB | - |