제출 #293151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293151		Kastanda	고대 책들 (IOI17_books)	C++11	22 / 100	801 ms	159412 KiB

books

// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006, MXN = 1003;
int n, st, k, T[N], P[N], A[N], mn[N], mx[N], MC[N];
ll dp[MXN][MXN];
int mark[MXN][MXN];
vector < tuple < int , int , int > > E;
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        if (v == u)
                return ;
        P[u] = v;
        mn[v] = min(mn[v], mn[u]);
        mx[v] = max(mx[v], mx[u]);
}
inline void AddEdge(int v, int u, int w)
{
        E.push_back({w, v, u});
}

long long minimum_walk(vector < int > _A, int _st)
{
        n = (int)_A.size();
        st = _st + 1;
        for (int i = 1; i <= n; i ++)
                A[i] = _A[i - 1] + 1;

        ll SM = 0, tot = 0;
        for (int i = 1; i <= n; i ++)
                SM += abs(A[i] - i);
        memset(P, -1, sizeof(P));
        for (int i = 1; i <= n; i ++)
                mn[i] = mx[i] = i;
        set < int > ST;
        for (int i = 1; i <= n; i ++)
                ST.insert(i);

        vector < int > M(n + 1, 0);
        vector < pair < int , int > > Roller;
        for (int i = 1; i <= n; i ++)
                if (!M[i] && A[i] != i)
                {
                        auto Do = [&](int l, int r){
                                if (l >= r)
                                        return ;
                                auto it = ST.lower_bound(l);
                                while (it != ST.end() && * it < r)
                                        Merge(* it, (* it) + 1), it = ST.erase(it);
                                return ;
                        };

                        vector < int > V;
                        int nw = i;
                        while (!M[nw])
                                V.push_back(nw), M[nw] = 1, nw = A[nw];
                        sort(V.begin(), V.end());
                        int is = 0;
                        for (int j : V)
                                if (j == st)
                                        is = 1;
                        for (int j = 0; j + 1 < (int)V.size(); j ++)
                        {
                                if (V[j + 1] < st || V[j] > st || is)
                                        Do(V[j], V[j + 1]);
                                else
                                        Roller.push_back({V[j], V[j + 1]});
                        }
                }

        /*
        for (int i = 1; i <= n; i ++)
                if (i != A[i])
                {
                                        int l = min(i, A[i]);
                        int r = max(i, A[i]);

                        Do(l, min(r, st - 1));
                        Do(max(st + 1, l), r);
                }
        */
        vector < pair < pair < int , int > , int > > vec;
        for (int i = 1; i <= n; i ++)
                if ((Find(i) == i && i != A[i]))
                        vec.push_back({{mn[i], mx[i]}, i});
        if (Find(st) == st && A[st] == st)
        {
                //T[st] = ++ k;
                vec.push_back({{st, st}, st});
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < (int)vec.size(); i ++)
                T[vec[i].second] = i;



        //assert(Find(st) == st);
        /*for (int i = 1; i <= n; i ++)
                if (i != A[i])
                {
                        int l = min(i, A[i]);
                        int r = max(i, A[i]);

                        if (l <= st && st <= r)
                                AddEdge(T[Find(l)], T[Find(r)], 0);
                }*/

        memset(MC, -1, sizeof(MC));
        for (auto X : Roller)
        {
                int v = Find(X.first);
                int u = Find(X.second);
                MC[T[v]] = T[u];
                MC[T[u]] = T[v];
                //AddEdge(T[v], T[u], 0);
        }
/*
        for (auto X : vec)
                printf("%d , %d :: %d\n", X.first.first, X.first.second, X.second);

        for (int i = 0; i < (int)vec.size(); i ++)
                printf("%d ", MC[i]);
        printf("\n");
*/
        if (n <= 1000)
        {
                memset(dp, 63, sizeof(dp));
                int now = -1;
                for (int i = 0; i < (int)vec.size(); i ++)
                        if (vec[i].first.first <= st && vec[i].first.second >= st)
                                now = i;
                assert(now != -1);
                dp[now][now] = 0;
          assert(MC[now] == -1);
                mark[now][now] = 1;
                int sz = (int)vec.size();
                for (int l = now; l >= 0; l --)
                        for (int r = now; r < sz; r ++)
                        {
                                if (!mark[l][r])
                                        continue;
                                //printf("%d :: %d\n", l, r);
                                if (l > 0)
                                {
                                        ll d = dp[l][r] + vec[l].first.first - vec[l - 1].first.second;
                                        int le = l;
                                        int ri = r;
                                        int mn = l - 1;
                                        int mx = r;
                                        while (le > mn || ri < mx)
                                        {
                                                if (le > mn)
                                                {
                                                        le --;
                                                        if (MC[le] != -1)
                                                                mn = min(mn, MC[le]), mx = max(mx, MC[le]);
                                                }
                                                if (ri < mx)
                                                {
                                                        ri ++;
                                                        if (MC[ri] != -1)
                                                                mn = min(mn, MC[ri]), mx = max(mx, MC[ri]);
                                                }
                                        }
                                        dp[le][ri] = min(dp[le][ri], d);
                                        mark[le][ri] = 1;
                                }
                                if (r + 1 < sz)
                                {
                                        ll d = dp[l][r] + vec[r + 1].first.first - vec[r].first.second;
                                        int le = l;
                                        int ri = r;
                                        int mn = l;
                                        int mx = r + 1;
                                        while (le > mn || ri < mx)
                                        {
                                                if (le > mn)
                                                {
                                                        le --;
                                                        if (MC[le] != -1)
                                                                mn = min(mn, MC[le]), mx = max(mx, MC[le]);
                                                }
                                                if (ri < mx)
                                                {
                                                        ri ++;
                                                        if (MC[ri] != -1)
                                                                mn = min(mn, MC[ri]), mx = max(mx, MC[ri]);
                                                }
                                        }
                                        dp[le][ri] = min(dp[le][ri], d);
                                        mark[le][ri] = 1;

                                }
                        }
                tot = dp[0][sz - 1] * 2;
                return SM + tot;

        }
        assert(0);

        for (int i = 0; i + 1 < k; i ++)
                AddEdge(vec[i].second, vec[i + 1].second, vec[i + 1].first.first - vec[i].first.second);

        sort(E.begin(), E.end());
        memset(P, -1, sizeof(P));
        int cc = 0;
        for (auto X : E)
        {
                int w, v, u;
                tie(w, v, u) = X;
                v = Find(v);
                u = Find(u);
                if (v == u)
                        continue;
                tot += w * 2;
                Merge(v, u);
                cc ++;
        }
        assert(cc == k - 1);

        tot = tot + SM;
        return tot;

        /*while (vec.size() > 1 && vec[(int)vec.size() - 2].second >= st)
                tot += vec.back().first - vec[(int)vec.size() - 2].second, vec.pop_back();
        if (vec.size() && vec.back().first >= st)
                tot += vec.back().first - st, vec.pop_back();
        reverse(vec.begin(), vec.end());
        while (vec.size() > 1 && vec[(int)vec.size() - 2].first <= st)
                tot += vec[(int)vec.size() - 2].first - vec.back().second, vec.pop_back();
        if (vec.size() && vec.back().second <= st)
                tot += st - vec.back().second, vec.pop_back();
        if (vec.size())
        {
                assert(vec.size() == 1 && vec[0].first <= st && st <= vec[0].second);
                if (A[st] == st)
                {
                        int l = st;
                        while (l && A[l] == l)
                                l --;
                        assert(l >= vec[0].first);
                        int Best = st - l;
                        int r = st;
                        while (r <= n && A[r] == r)
                                r ++;
                        assert(r <= vec[0].second);
                        Best = min(Best, r - st);
                        tot += Best;
                }
        }

        tot = tot * 2 + SM;
        return tot;*/
}

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