Submission #271827

#	Time	Username	Problem	Language	Result	Execution time	Memory
271827		hamerin	고대 책들 (IOI17_books)	C++17	0 / 100	103 ms	1532 KiB

books

#include "books.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

i64 minimum_walk(vector<int> p, int s) {
    const int N = p.size();

    vector<vector<int>> cycles;
    vector<int> cyc(N);

    vector<bool> vst(N);
    for (int i = 0; i < N; i++) {
        if (vst[i]) continue;

        cycles.emplace_back(vector<int>());

        int cur = i;
        while (cycles.back().empty() || cur != i) {
            cycles.back().emplace_back(cur);
            cyc[cur] = cycles.size() - 1;
            vst[cur] = true;
            cur = p[cur];
        }
    }
    for (auto &vec : cycles) sort(iterall(vec));

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

    vector<ti> intervals;
    for (int i = 0; i < cycles.size(); i++) {
        const auto &v = cycles[i];
        intervals.emplace_back(v.front(), v.back(), i);
    }
    sort(iterall(intervals));


    const int I = intervals.size();

    vector<int> mp(I);
    for (int i = 0; i < I; i++) mp[get<2>(intervals[i])] = i;
    for (int i = 0; i < I; i++) cyc[i] = mp[cyc[i]];

    vector<vector<int>> newcycles(I);
    for (int i = 0; i < I; i++) newcycles[i] = cycles[get<2>(intervals[i])];
    cycles = newcycles;
    newcycles.clear();

    // interval 합치기
    deque<pi> newIntervals;
    for (auto [l, r, _] : intervals) {
		if (!newIntervals.empty() && newIntervals.back().second > l) {
            newIntervals.back().second = max(newIntervals.back().second, r);
        } else {
            newIntervals.emplace_back(l, r);
        }
    }

    while (!newIntervals.empty() &&
           newIntervals.back().first == newIntervals.back().second)
        newIntervals.pop_back();

    while (!newIntervals.empty() &&
           newIntervals.front().first == newIntervals.front().second)
        newIntervals.pop_front();

    for (int i = 0; i < (int)newIntervals.size() - 1; i++) {
        ans += 2 * (newIntervals[i + 1].first - newIntervals[i].second);
    }

    if (newIntervals.empty()) return ans;


    // Strategy
    // Disjoint Set의 Lmost, Rmost interval까지의 거리 저장
    // Recursive하게 dp로 해결 가능할 듯

    auto iter = lower_bound(iterall(newIntervals), pi(s, 2000000));
    if (iter == newIntervals.begin()) {
        ans += 2 * (iter->first - s);
        return ans;
    }

    --iter;
    if (iter->second < s) {
        ans += 2 * (s - iter->second);
        return ans;
    }

    auto LMost = iter->first;
    auto RMost = iter->second;

    int idxL = find_if(iterall(intervals),
                       [LMost](ti x) { return get<0>(x) == LMost; }) -
               intervals.begin();
    int idxR = find_if(iterall(intervals),
                       [RMost](ti x) { return get<1>(x) == RMost; }) -
               intervals.begin();
    int idxS = find_if(iterall(intervals),
                       [s](ti x) { return get<0>(x) <= s && s <= get<1>(x); }) -
               intervals.begin();


    function<i64(int, int)> distanceF = [&](int a, int b) {
        auto &v1 = cycles[a];
        auto &v2 = cycles[b];

        vector<pi> mer;
        for (auto el : v1) mer.emplace_back(el, 0);
        for (auto el : v2) mer.emplace_back(el, 1);
        sort(iterall(mer), [](pi l, pi r) { return l.first < r.first; });

        int ret = 3000000;
        for (int i = 0; i < mer.size() - 1; i++) {
            if (mer[i].second + mer[i + 1].second == 1)
                ret = min(ret, mer[i + 1].first - mer[i].first);
        }

        return ret;
    };

    function<vector<i64>(int)> dijkstra = [&](int sv) {
        vector<i64> dist(N, numeric_limits<i64>::max() / 3);
        priority_queue<pli, vector<pli>, greater<>> pq;
        dist[sv] = 0;
        pq.emplace(0, sv);

        while (!pq.empty()) {
            auto [W, u] = pq.top();
            pq.pop();

            if (W > dist[u]) continue;
            for (int v = 0; v < N; v++) {
                if (!(LMost <= get<0>(intervals[v]) &&
                      get<1>(intervals[v]) <= RMost))
                    continue;

                i64 w = distanceF(u, v);
                if (dist[v] > W + w) {
                    pq.emplace(W + w, v);
                    dist[v] = W + w;
                }
            }
        }

        return dist;
    };

    auto dist = dijkstra(idxS);
    ans += 2 * dist[idxL];
    ans += 2 * dist[idxR];

    return ans;
}

Compilation message (stderr)

books.cpp: In function 'i64 minimum_walk(std::vector<int>, int)':
books.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < cycles.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
books.cpp: In lambda function:
books.cpp:129:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = 0; i < mer.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~~

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