Submission #406889

#	Time	Username	Problem	Language	Result	Execution time	Memory
406889		ja_kingy	Ancient Books (IOI17_books)	C++14	100 / 100	221 ms	34952 KiB

books

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

typedef pair<int,int> pii;

long long minimum_walk(vector<int> p, int s) {
	long long ans = 0;
	int n = p.size(), ccnt = 0;
	vector<int> mn(n), mx(n), cyc(n);
	vector<pii> evs;
	for (int i = 0; i < n; ++i) {
		ans += abs(i-p[i]);
		if (!cyc[i]) {
			ccnt++;
			cyc[i] = ccnt;
			mn[ccnt] = mx[ccnt] = i;
			for (int x = p[i]; x != i; x = p[x]) {
				cyc[x] = ccnt;
				mn[ccnt] = min(mn[ccnt], x);
				mx[ccnt] = max(mx[ccnt], x);
			}
			if (mn[ccnt] != mx[ccnt] || i == s) {
				evs.push_back({mn[ccnt], -1});
				evs.push_back({mx[ccnt], 1});
			}
		}
	}
	sort(evs.begin(), evs.end());
	int rcnt = 0, pv = -1, fst;
	for (pii ev: evs) {
		if (rcnt == 0 && ~pv) {
			fst = ev.first;
			ans += (ev.first - pv) * 2;
		}
		rcnt -= ev.second;
		pv = ev.first;
		if (rcnt == 0 && fst <= s && s <= pv) {
			//cerr << rcnt << ' ' << fst << ' ' << pv << endl;
			int cl = s, cr = s, l = mn[cyc[s]], r = mx[cyc[s]];
			for (;;) {
				// cerr << l << ' ' << r << endl;
				while (cl != l || cr != r) {
					if (cl != l) {
						cl--;
						l = min(l, mn[cyc[cl]]);
						r = max(r, mx[cyc[cl]]);
					} else {
						cr++;
						l = min(l, mn[cyc[cr]]);
						r = max(r, mx[cyc[cr]]);
					}
				}
				if (l == fst || r == pv) break;
				ans+=2;
				l--;
				r++;
			}
		}
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:54:5: warning: 'fst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     if (l == fst || r == pv) break;
      |     ^~

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