oj.uz

Submission #271865

# Submission time Handle Problem Language Result Execution time Memory
271865 2020-08-18T07:46:41 Z hamerin Ancient Books (IOI17_books) C++17
22 / 100
 2000 ms 37232 KB 
#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(I, 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 < I; 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 * min(dist[idxL], dist[idxR]);
    // ans += 2 * dist[idxR];

    return ans;
}

Compilation message

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:128: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]
  128 |         for (int i = 0; i < mer.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 80 ms 632 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 80 ms 632 KB Output is correct
30 Execution timed out 2076 ms 37232 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 1032 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 80 ms 632 KB Output is correct
30 Execution timed out 2076 ms 37232 KB Time limit exceeded
31 Halted 0 ms 0 KB -