oj.uz

Submission #921319

# Submission time Handle Problem Language Result Execution time Memory
921319 2024-02-03T17:10:02 Z salmon Ancient Books (IOI17_books) C++14
0 / 100
 1 ms 6492 KB 
#include <bits/stdc++.h>
using namespace std;

int parent[1100100];
int v[1100100];
bool done[1100100];
int l[1100100];
int r[1100100];

pair<int,int> expand_range(int l2, int r2, int h){
    int l1 = min(l2,h);
    int r1 = max(r2,h);

    while(l1 != l2 || r1 != r2){
        if(l1 != l2){
            l2--;
            l1 = min(l1,l[parent[l2]]);
            r1 = max(r1,r[parent[l2]]);
        }
        else{
            r2++;
            l1 = min(l1,l[parent[r2]]);
            r1 = max(r1,r[parent[r2]]);
        }
    }

    return {l2,r2};
}

long long minimum_walk(vector<int> p, int s) {
    int l1 = s;
    int r1 = s;
    int l2 = s;
    int r2 = s;
    long long int some = 0;

    int N = p.size();

    for(int i = 0; i < N; i++){
        done[i] = false;
    }

    for(int i = 0; i < N; i++){
        if(done[i]) continue;

        l[i] = i;
        r[i] = i;
        parent[i] = i;
        int j = p[i];
        some += abs(i - j);
        while(j != i){
            int temp = j;
            parent[j] = i;
            done[j] = true;
            r[i] = max(r[i],j);
            j = p[j];
            some += abs(temp - j);
        }
    }

    l2 = l[parent[s]];
    r2 = r[parent[s]];

    while(l1 != l2 || r1 != r2){
        if(l1 != l2){
            l1--;
            l2 = min(l2,l[parent[l1]]);
            r2 = max(r2,r[parent[l1]]);
        }
        else{
            r1++;
            l2 = min(l2,l[parent[r1]]);
            r2 = max(r2,r[parent[r1]]);
        }
    }

    int l3l = l1;
    int r3l = r1;

    int l3r = l1;
    int r3r = r1;

    while(l1 != 0 || r1 != N - 1){
        l3l = l1;
        r3l = r1;

        l3r = l1;
        r3r = r1;

        int tcoft = 0;
        int coft = 0;

        while(!(r1 < r3l && l3r < l1)){
            coft += 2;
            tcoft += 2;

            if(l3l > 0){
                pair<int,int> ii = expand_range(l3l,r3l,l3l - 1);
                l3l = ii.first;
                r3l = ii.second;
                tcoft -= 2;
            }

            if(r3r < N - 1){
                pair<int,int> ii = expand_range(l3r,r3r,r3r+1);
                l3r = ii.first;
                r3r = ii.second;
                tcoft -= 2;
            }

            if(!(r1 < r3l && l3r < l1) && l3l == 0 && r3r == N - 1){
                some += tcoft;
                break;
            }
        }

        some += coft;
        l1 = min(l3l,l1);
        l1 = min(l3r,l1);


        r1 = max(r3l,r1);
        r1 = max(r3r,r1);
    }

    return some;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3506'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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