Submission #137331

#	Time	Username	Problem	Language	Result	Execution time	Memory
137331		choikiwon	Ancient Books (IOI17_books)	C++17	100 / 100	511 ms	38736 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1000010;

int N, S;
int A[maxn], vis[maxn];
vector<pii> V;

int fa[maxn], le[maxn], ri[maxn];
void init() {
    for(int i = 0; i < N; i++) {
        fa[i] = i;
        le[i] = i;
        ri[i] = i;
    }
}
int find(int u) {
    if(fa[u] == u) return u;
    else return fa[u] = find(fa[u]);
}
void mrg(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v) return;
    fa[v] = u;
    le[u] = min(le[u], le[v]);
    ri[u] = max(ri[u], ri[v]);
}

ll minimum_walk(std::vector<int> p, int s) {
	N = p.size();
	S = s;
	for(int i = 0; i < N; i++) {
        A[i] = p[i];
	}

	init();

	ll ret = 0;
	for(int i = 0; i < N; i++) {
        if(vis[i]) continue;
        if(A[i] == i) {
            if(i == S) V.push_back(pii(S, S));
            continue;
        }

        int mx = -1e9;

        int u = i;
        while(!vis[u]) {
            vis[u] = 1;
            mx = max(mx, u);

            ret += abs(u - A[u]);
            mrg(u, A[u]);
            u = A[u];
        }

        V.push_back(pii(i, mx));
	}

	if(V.size() == 0) return ret;

	int st = V[0].first;
	int ed = V[0].second;

	pii dest;
	for(int i = 1; i < V.size(); i++) {
        if(ed < V[i].first) {
            ret += 2 * (V[i].first - ed);

            if(st <= S && S <= ed) {
                dest = pii(st, ed);
            }

            st = V[i].first;
            ed = V[i].second;
            continue;
        }
        ed = max(ed, V[i].second);
	}

	if(st <= S && S <= ed) {
        dest = pii(st, ed);
	}

	int l = S;
	int r = S;
	int mn = 1e9;
	int mx = -1e9;
	while(l != dest.first || r != dest.second) {
        mn = min(mn, le[find(l)]);
        mn = min(mn, le[find(r)]);
        mx = max(mx, ri[find(l)]);
        mx = max(mx, ri[find(r)]);

        if(mn == l && mx == r) {
            l--;
            r++;
            ret += 2;
            continue;
        }
        if(mn < l) {
            l--;
            continue;
        }
        if(r < mx) {
            r++;
            continue;
        }
	}

	return ret;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < V.size(); i++) {
                 ~~^~~~~~~~~~

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