Submission #798449

#	Time	Username	Problem	Language	Result	Execution time	Memory
798449		PixelCat	Ancient Books (IOI17_books)	C++14	42 / 100	132 ms	56416 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>;

const int MAXN = 1000;
const int INF = 1e18;

int nxtl[MAXN + 10][MAXN + 10];
int nxtr[MAXN + 10][MAXN + 10];
int ll[MAXN + 10];
int rr[MAXN + 10];
int dp[MAXN + 10][MAXN + 10];

int solve(int l, int r, int L, int R) {
    if(l < L || r > R) return INF;
    if(dp[l][r] != -1) return dp[l][r];
    if(l == L && r == R) return dp[l][r] = 0;
    if(nxtl[l][r] != l || nxtr[l][r] != r) {
        return dp[l][r] = solve(nxtl[l][r], nxtr[l][r], L, R);
    }
    int cl = l - ll[l];
    int cr = rr[r] - r;
    dp[l][r] = min(
        solve(ll[l], r, L, R) + cl * 2,
        solve(l, rr[r], L, R) + cr * 2
    );
    return dp[l][r];
}

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;

    ll[0] = -1e10;
    For(i, 1, n - 1) {
        if(cid[i - 1] >= 0) ll[i] = i - 1;
        else ll[i] = ll[i - 1];
    }
    rr[n - 1] = 1e10;
    Forr(i, n - 2, 0) {
        if(cid[i + 1] >= 0) rr[i] = i + 1;
        else rr[i] = rr[i + 1];
    }

    For(i, 0, n - 1) {
        if(cid[i] >= 0) {
            nxtl[i][i] = range[cid[i]].F;
            nxtr[i][i] = range[cid[i]].S;
        } else {
            nxtl[i][i] = i;
            nxtr[i][i] = i;
        }
    }
    Forr(i, n - 1, 0) For(j, i + 1, n - 1) {
        nxtl[i][j] = min(nxtl[i][j - 1], nxtl[i + 1][j]);
        nxtr[i][j] = max(nxtr[i][j - 1], nxtr[i + 1][j]);
    }

    int L = 0, R = n - 1;
    while(cid[L] == -1) L++;
    while(cid[R] == -1) R--;
    L = min(L, (int)s);
    R = max(R, (int)s);
    cerr << L << " " << R << "\n";

    memset(dp, -1, sizeof(dp));
    return ans + solve(s, s, L, R);
}

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