Submission #1061081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061081		onbert	Ancient Books (IOI17_books)	C++17	22 / 100	2052 ms	158112 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, INF = 1e9;
int p[maxn];
int vis[maxn];
bool taken[maxn];

int minimum_walk(vector<int32_t> P, int32_t s) {
    int n = P.size();
    for (int i=0;i<n;i++) p[i] = P[i];
    for (int i=0;i<n;i++) vis[i] = false;
    int ans = 0, cnt = 0;
    vector<pair<int,int>> vec = {{-1, -1}};
    for (int i=0;i<n;i++) if (!vis[i]) {
        if (p[i]==i && i==s) {
            cnt++;
            vis[i] = cnt;
            vec.push_back({s, s});
        }
        if (p[i]==i) continue;
        int u = i;
        pair<int,int> val = {u, u};
        cnt++;
        while (true) {
            vis[u] = cnt;
            val.first = min(u, val.first);
            val.second = max(u, val.second);
            int v = p[u];
            ans += abs(v-u);
            if (v==i) break;
            u = v;
        }
        vec.push_back(val);
    }

    if (vec.size()==1) return ans;

    sort(vec.begin(), vec.end());
    int lastl = vec[1].first, mx = vec[1].second;
    int LL = 0, RR = n-1;
    for (int i=2;i<vec.size();i++) {
        if (vec[i].first > mx) {
            if (lastl<=s && s<=mx) {
                LL = lastl, RR = mx;
                break;
            }
            lastl = vec[i].first;
        }
        mx = max(vec[i].second, mx);
    }
    // cout << LL << " " << RR << endl;

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({vis[s], 0});
    int dist[cnt+5];
    for (int i=1;i<=cnt;i++) dist[i] = -1;
    while (pq.size() > 0) {
        int u = pq.top().first, d = pq.top().second;
        pq.pop();
        if (vec[u].second < LL || vec[u].first > RR) dist[u] = -2;
        if (dist[u]!=-1) continue;
        dist[u] = d;
        for (int i=vec[u].first; i<=vec[u].second;i++) {
            if (dist[vis[i]]==-1) pq.push({vis[i], d});
        }
        for (int i=vec[u].first-1;i>=0;i--) {
            if (p[i]!=i) {
                if (dist[vis[i]]==-1) pq.push({vis[i], d + (vec[u].first - i)*2});
            }
        }
        for (int i=vec[u].second+1;i<n;i++) {
            if (p[i]!=i) {
                if (dist[vis[i]]==-1) pq.push({vis[i], d + (i - vec[u].first)*2});
            }
        }
    }
    int MX = 0;
    for (int i=1;i<=cnt;i++) if (dist[i]!=-1) MX = max(dist[i], MX);
    ans += MX;

    vector<pair<int,int>> vec2;
    for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
    vec2.push_back({LL, RR});
    sort(vec2.begin(), vec2.end());
    mx = vec2[1].second;
    for (int i=2;i<vec2.size();i++) {
        if (vec2[i].first > mx) ans += (vec2[i].first - mx)*2;
        mx = max(vec2[i].second, mx);
    }
    return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int32_t)':
books.cpp:43:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=2;i<vec.size();i++) {
      |                  ~^~~~~~~~~~~
books.cpp:88:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i=2;i<vec2.size();i++) {
      |                  ~^~~~~~~~~~~~

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