Submission #1061057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061057		onbert	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	4444 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];
vector<pair<int,int>> vec = {{-1, -1}};
int l, r;

void expand(int L, int R) {
    vector<int> add;
    while (l > L) {
        l--;
        if (p[l]!=l) add.push_back(vis[l]);
    }
    while (r<R) {
        r++;
        if (p[r]!=r) add.push_back(vis[r]);
    }
    for (int i:add) expand(vec[i].first, vec[i].second);
}

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;
    int cnt = 0;
    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);
    }

    sort(vec.begin(), vec.end());
    int lastl = 0, mx = 0;
    int LL, RR;
    for (int i=1;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);
    }

    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 (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});
                break;
            }
        }
        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});
                break;
            }
        }
    }
    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[0].second;
    for (int i=1;i<vec2.size();i++) {
        if (vec2[i].first > mx) ans += vec2[i].first - mx;
        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:56: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]
   56 |     for (int i=1;i<vec.size();i++) {
      |                  ~^~~~~~~~~~~
books.cpp:101: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]
  101 |     for (int i=1;i<vec2.size();i++) {
      |                  ~^~~~~~~~~~~~
books.cpp:97:36: warning: 'RR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
      |                               ~~~~~^~~~~~~
books.cpp:97:27: warning: 'LL' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     for (auto [x, y]:vec) if (y<LL || x>RR) vec2.push_back({x, y});
      |                           ^~

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