oj.uz

Submission #228099

# Submission time Handle Problem Language Result Execution time Memory
228099 2020-04-29T21:26:50 Z VEGAnn Ancient Books (IOI17_books) C++14
20 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#include "books.h"
//#include "grader.h"
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
bool mrk[N];
queue<int> q;
ll ans = 0, cl, cr, extra;
int n, le, ri, mem_l[N], mem_r[N], il[N], ir[N], loc_l, loc_r, S, P[N];

void extend(){
    while (sz(q)){
        int v = q.front(); q.pop();

        int nl = v, nr = P[v];

        if (nl > nr) swap(nl, nr);

        if (nl < le){
            for (int j = nl; j < le; j++)
                q.push(j);
            le = nl;
        }

        if (nr > ri){
            for (int j = ri + 1; j <= nr; j++)
                q.push(j);
            ri = nr;
        }
    }
}

void get_lf(){
    int lst = le;
    loc_l = -1;
    cl = 0;

    for (int i = le - 1; i >= 0; i--){
        if (i < lst) cl += 2;

        if (mem_l[i] >= 0)
            lst = min(lst, mem_l[i]);

        if (ir[i] > S){
            loc_l = i;
            return;
        }
    }
}

void get_rt(){
    int lst = ri;
    loc_r = -1;
    cr = 0;

    for (int i = ri + 1; i < n; i++){
        if (i > lst) cr += 2;

        if (mem_r[i] >= 0)
            lst = max(lst, mem_r[i]);

        if (il[i] < S){
            loc_r = i;
            return;
        }
    }
}

long long minimum_walk(std::vector<int> p, int s) {
    n = sz(p);
    S = s;

    bool was = 0;

    fill(mem_l, mem_l + n, -1);
    fill(mem_r, mem_r + n, -1);

    for (int i = 0; i < n; i++){
        P[i] = p[i];
        ans += abs(p[i] - i);

        if (p[i] != i) {
            was = 1;
            int lf = i;
            int rt = p[i];

            if (lf > rt) swap(lf, rt);

            mem_l[rt] = lf;
            mem_r[lf] = rt;
        }

        if (mrk[i]) continue;

        int cr = i, mn = i, mx = i;

        while (!mrk[cr]){
            mn = min(mn, cr);
            mx = max(mx, cr);
            mrk[cr] = 1;
            cr = p[cr];
        }

        il[i] = mn;
        ir[i] = mx;

        cr = p[i];

        while (cr != i){
            il[cr] = mn;
            ir[cr] = mx;
            cr = p[cr];
        }
    }

    if (!was) return 0;

    for (int i = 0; i < n; i++)
        if (p[i] != i)
            break;
        else extra += 2;

    for (int i = n - 1; i >= 0; i--)
        if (p[i] != i)
            break;
        else extra += 2;

    le = ri = s;

    q.push(s);

    extend();

    while (1){
        get_lf();
        get_rt();

        if (loc_l < 0) {
            ans += cl + cr - extra;
            break;
        }

        ans += min(cl, cr);

        for (int j = loc_l; j < le; j++)
            q.push(j);
        le = loc_l;

        extend();
    }

	return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
0 / 30.0

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