제출 #313348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313348		hhh07	고대 책들 (IOI17_books)	C++14	0 / 100	1 ms	384 KiB

books

#include <iostream>
#include <vector>
#include "books.h"

using namespace std;

typedef vector<int> vi;

void extend(int &l, int &r, vi C, vi L, vi R){
    int ll = l, rr = r;
    ll = min(ll, min(L[C[l]], L[C[r]]));
    rr = max(rr, max(R[C[l]], R[C[r]]));
    
    while(ll < l || r < rr){
        if (ll < l){ // sve dok ll "bjezi" tj dok se nalazi min smanjivat ce se i l
            l--; // l == ll kad ne mogne dalje tj kad L[C[l]] dodje do najljevljeg moguceg
            ll = min(ll, L[C[l]]);
            rr = max(rr, R[C[l]]);
        }
        else{
            r++;
            ll = min(ll, L[C[r]]);
            rr = max(rr, R[C[r]]);
        }
    }
        
}

int connect(int l, int r, int target_l, int target_r, vi &C, vi &L, vi &R){
    int cost = 0;
    while(l > target_l || r < target_r){
        extend(l, r, C, L, R);
        bool next_l = false;
        int cost_l = 0;
        int l_l = l, r_l = r;
        while(true){
            if (l_l <= target_l)
                break;
            l_l--;
            cost_l += 2;
            extend(l_l, r_l, C, L, R);
            if (r_l > r){
                next_l = true;
                break;
            }
        }
        bool next_r = false;
        int cost_r = 0;
        int l_r = l, r_r = r;
        while(true){
            if (r_r >= target_r)
                break;
            r_r++;
            cost_r += 2;
            extend(l_r, r_r, C, L, R);
            if (l_r < l){
                next_r = true;
                break;
            }
        }
        if (next_l && next_r)
            cost += min(cost_l, cost_r);
        else
            cost += cost_l + cost_r;
        l = min(l_l, l_r);
        r = max(r_l, r_r);
    }
    
    return cost;
}

long long booksort(int n, int s, vector<int> order){
    long long res = 0;
    
    vector<int> C(n, -1), L(n), R(n);
    int l = s, r = s;
    int c = 0;
    
    for (int i = 0; i < n; i++){
        res += abs(i - order[i]);
        if (C[i] == -1){
            L[c] = i; R[c] = i;
            int j = order[i];
            while(i != j){
                C[j] = c;
                R[c] = max(R[c], j);
                j = order[j];
            }
            if (i != order[i]){
                l = min(l, L[c]);
                r = max(r, R[c]);
            }
            c++;
        }
    }
    
    return res + connect(s, s, l, r, C, L, R);
}

long long minimum_walk(vi order, int s){
    int n = order.size();
    return booksort(n, s, order);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30