Submission #798427

#	Time	Username	Problem	Language	Result	Execution time	Memory
798427		PixelCat	Ancient Books (IOI17_books)	C++14	50 / 100	141 ms	39804 KiB

books

#include "books.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

LL minimum_walk(vector<i32> p, i32 s) {
    assert(s >= 0);
    int n = sz(p);

    int ans = 0;
    vector<int> cid(n, -1);
    vector<pii> range;
    For(i, 0, n - 1) if(p[i] != i && cid[i] == -1) {
        int cur = i;
        int l = n + 1;
        int r = -1;
        do {
            l = min(l, cur);
            r = max(r, cur);
            ans += abs(p[cur] - cur);
            cur = p[cur];
            cid[cur] = sz(range);
        } while(cur != i);
        range.eb(l, r);
    }
    if(sz(range) == 0) return 0;

    vector<int> nxtr(n), nxtl(n);
    nxtl[0] = -1e10;
    For(i, 1, n - 1) {
        if(cid[i - 1] >= 0) nxtl[i] = i - 1;
        else nxtl[i] = nxtl[i - 1];
    }
    nxtr[n - 1] = 1e10;
    Forr(i, n - 2, 0) {
        if(cid[i + 1] >= 0) nxtr[i] = i + 1;
        else nxtr[i] = nxtr[i + 1];
    }

    int ll = 0, rr = n - 1;
    while(p[ll] == ll) ll++;
    while(p[rr] == rr) rr--;
    ll = min(ll, (int)s);
    rr = max(rr, (int)s);

    int l, r;
    l = s; r = s;
    queue<int> que;
    if(cid[s] >= 0) que.emplace(cid[s]);
    while(l > ll || r < rr) {
        pii rg;
        if(!que.empty()) {
            int id = que.front(); que.pop();
            rg = range[id];
        } else {
            int cl = l - nxtl[l];
            int cr = nxtr[r] - r;
            if(cl < cr) {
                ans += cl * 2;
                rg = pii(nxtl[l], r);
            } else {
                ans += cr * 2;
                rg = pii(l, nxtr[r]);
            }
        }
        while(l > rg.F) {
            l--;
            if(cid[l] >= 0) que.emplace(cid[l]);
        }
        while(r < rg.S) {
            r++;
            if(cid[r] >= 0) que.emplace(cid[r]);
        }
    }
    return ans;
}

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