Submission #137400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137400	2019-07-27T15:50:01 Z	fredbr	Simurgh (IOI17_simurgh)	C++17	Compilation error	0 ms	0 KB

simurgh

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ii = pair<int, int>;
    
int const maxn = 1010;
ii dp[maxn];

ii dfs(vector<int> const& p, vector<int>& vis, int i) {
    if (vis[i] == 1) return dp[i];
    vis[i] = 1;
    ii ans = {i, i};

    ii get = {p.size(), -1};
    if (vis[p[i]] == 0) get = dfs(p, vis, p[i]);

    dp[i] = {min(get.first, ans.first), max(get.second, ans.second)};

    return dp[i];
}

ii dp3[maxn][maxn];

ii get(vector<int> const& p, vector<int>& vis, int l, int r) {
    if (dp3[l][r] != ii{-1, -1}) return dp3[l][r];

    if (l == r) return dp3[l][r] = dfs(p, vis, l);

    ii h = dfs(p, vis, r);
    ii g = get(p, vis, l, r-1);

    return dp3[l][r] = {min(g.first, h.first), max(g.second, h.second)};
}

int dp2[maxn][maxn];

int solve(vector<int> const& p, vector<int>& vis, int l, int r, int a, int b) {
    if (l < a or r > b) return maxn*maxn;
    if (l == a and r == b) return 0; 
    if (dp2[l][r] != -1) return dp2[l][r];

    int& d = dp2[l][r];
    d = 0;

    if (ii{l, r} != get(p, vis, l, r)) {
        ii ps = get(p, vis, l, r);
        return dp2[l][r] = solve(p, vis, ps.first, ps.second, a, b);
    }
    else return dp2[l][r] = min(2 + solve(p, vis, l-1, r, a, b), 
                                2 + solve(p, vis, l, r+1, a, b));
}

long long minimum_walk(std::vector<int> p, int s) {
    memset(dp2, -1, sizeof(dp2));
    for (int i = 0; i < maxn; i++)
        fill(dp3[i], dp3[i]+maxn, ii{-1, -1});

    int n = p.size();

	ll ans = 0;

    int a = s, b = s;
    for (int i = 0; i < n; i++) {
        if (p[i] != i) a = min(a, i), b = max(b, i);
    }

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

    vector<int> vis(n);

    ans += solve(p, vis, s, s, a, b);

    return ans;
}

Compilation message

simurgh.cpp:1:10: fatal error: books.h: No such file or directory
 #include "books.h"
          ^~~~~~~~~
compilation terminated.