Submission #581740

#	Time	Username	Problem	Language	Result	Execution time	Memory
581740		alirezasamimi100	Ancient Books (IOI17_books)	C++17	100 / 100	307 ms	34900 KiB

books

#include "books.h"
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

using ll = long long int;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

const int inf = 1.05e9;
const ll INF = 1e18;

ll minimum_walk(vector<int> p, int s) {
    ll ans = 0, mx = 0, mx1 = 0, mx2 = 0;
    int n = p.size(), l = s, r = s;
    ll d[n], g[n];
    memset(d, -1, sizeof d);
    memset(g, -1, sizeof g);
    d[s] = 0;
    queue<int> q[2];
    q[0].push(s);
    while(true){
        while(!q[0].empty()){
            int v = q[0].front();
            q[0].pop();
            for(int i = p[v]; d[i] == -1; i = p[i]){
                d[i] = d[v];
                q[0].push(i);
            }
            while(l > v){
                l--;
                if(d[l] == -1){
                    d[l] = d[v];
                    q[0].push(l);
                }
            }
            while(r < v){
                r++;
                if(d[r] == -1){
                    d[r] = d[v];
                    q[0].push(r);
                }
            }
            if(v && g[v - 1] == -1){
                g[v - 1] = d[v] + 1;
                q[1].push(v - 1);
            }
            if(v + 1 < n && g[v + 1] == -1){
                g[v + 1] = d[v] + 1;
                q[1].push(v + 1);
            }
        }
        if(q[1].empty()) break;
        int v = q[1].front();
        q[1].pop();
        if(d[v] != -1) continue;
        d[v] = g[v];
        for(int i = p[v]; d[i] == -1; i = p[i]){
            d[i] = d[v];
            q[0].push(i);
        }
        while(l > v){
            l--;
            if(d[l] == -1){
                d[l] = d[v];
                q[0].push(l);
            }
        }
        while(r < v){
            r++;
            if(d[r] == -1){
                d[r] = d[v];
                q[0].push(r);
            }
        }
        if(v && g[v - 1] == -1){
            g[v - 1] = d[v] + 1;
            q[1].push(v - 1);
        }
        if(v + 1 < n && g[v + 1] == -1){
            g[v + 1] = d[v] + 1;
            q[1].push(v + 1);
        }
    }
    for(int i = 0; i < n; i++){
        ans += abs(i - p[i]);
        if(i <= s && p[i] >= s) mx = max(mx, d[i]);
        if(i <= s && i != p[i]) mx1 = max(mx1, d[i]);
        if(i >= s && i != p[i]) mx2 = max(mx2, d[i]);
    }
    return ans + 2 * (mx1 + mx2 - mx);
}

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