Submission #799274

#	Time	Username	Problem	Language	Result	Execution time	Memory
799274		LittleCube	Ancient Books (IOI17_books)	C++17	22 / 100	2085 ms	240160 KiB

books

#pragma GCC optimize("Ofast,unroll-loops")
#include "books.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

vector<int> seg[4000005];
int n, rp[1000005], dn[1000005], d0[1000005], l, r;

void init()
{
	for (int i = 1; i <= 4 * n; i++)
		seg[i].clear();
}

void insert(int mL, int mR, int val, int i = 1, int L = 0, int R = n - 1)
{
	if (mL <= L && R <= mR)
		seg[i].emplace_back(val);
	else if (R < mL || mR < L)
		return;
	else
	{
		int mid = (L + R) / 2;
		insert(mL, mR, val, i << 1, L, mid);
		insert(mL, mR, val, i << 1 | 1, mid + 1, R);
	}
}

vector<int> query(int pos)
{
	vector<int> v;
	int i = 1, L = 0, R = n - 1;
	while (1)
	{
		while (!seg[i].empty())
		{
			v.emplace_back(seg[i].back());
			seg[i].pop_back();
		}
		if (L == R)
			break;
		int mid = (L + R) / 2;
		if (pos <= mid)
			R = mid, i = i << 1;
		else
			L = mid + 1, i = i << 1 | 1;
	}
	return v;
}

long long minimum_walk(std::vector<int> p, int s)
{
	n = p.size();
	l = 0, r = n - 1;
	while (l < n && p[l] == l)
		l++;
	if (l == n)
		return 0;
	while (r && p[r] == r)
		r--;

	ll ans = 0;
	if (s < l)
	{
		ans += 2 * (l - s);
		s = l;
	}
	if (r < s)
	{
		ans += 2 * (s - r);
		s = r;
	}
	for (int i = 0; i < n; i++)
		ans += abs(p[i] - i);
	for (int i = 0; i < n; i++)
		rp[p[i]] = i;

	cerr << "calc n\n";
	// calc n
	{
		for (int i = 0; i < n; i++)
			dn[i] = -1;
		for (int i = 0; i < n; i++)
		{
			int l = min({i, p[i], rp[i]}), r = max({i, p[i], rp[i]});
			insert(l, r, i);
		}
		vector<int> cur, nxt = {r};
		dn[r] = 0;
		int d = 0;
		while (!nxt.empty())
		{
			swap(nxt, cur);
			nxt.clear();
			for (int i = 0; i < cur.size(); i++)
			{
				vector<int> v = query(cur[i]);
				for (int j : v)
					if (dn[j] == -1)
						dn[j] = d, cur.emplace_back(j);
			}
			d++;
			for (int i : cur)
			{
				if (i - 1 >= 0 && dn[i - 1] == -1)
					dn[i - 1] = d, nxt.emplace_back(i - 1);
				if (i + 1 < n && dn[i + 1] == -1)
					dn[i + 1] = d, nxt.emplace_back(i + 1);
			}
		}
	}

	// calc 0
	{
		init();
		for (int i = 0; i < n; i++)
			d0[i] = -1;
		for (int i = 0; i < n; i++)
		{
			int l = min({i, p[i], rp[i]}), r = max({i, p[i], rp[i]});
			insert(l, r, i);
		}
		vector<int> cur, nxt = {l};
		d0[l] = 0;
		int d = 0;
		while (!nxt.empty())
		{
			swap(nxt, cur);
			nxt.clear();
			for (int i = 0; i < cur.size(); i++)
			{
				vector<int> v = query(cur[i]);
				for (int j : v)
					if (d0[j] == -1)
						d0[j] = d, cur.emplace_back(j);
			}
			d++;
			for (int i : cur)
			{
				if (i - 1 >= 0 && d0[i - 1] == -1)
					d0[i - 1] = d, nxt.emplace_back(i - 1);
				if (i + 1 < n && d0[i + 1] == -1)
					d0[i + 1] = d, nxt.emplace_back(i + 1);
			}
		}
	}

	int sec = 1e9;

	// check next nearest
	auto check = [&](int t)
	{
		int cl, cr, nl, nr, d, d0n = 1e9;
		cl = cr = nl = nr = t;
		d = abs(t - s);
		auto getin = [&](int i)
		{
			cl = min({cl, i, p[i], rp[i]}), cr = max({cr, i, p[i], rp[i]});
			d0n = min(d0n, d0[i] + dn[i]);
		};
		while (l < cl || cr < r)
		{
			while (cl <= nl || nr <= cr)
			{
				if (cl <= nl)
					getin(nl--);
				if (nr <= cr)
					getin(nr++);
			}
			sec = min(sec, d + d0n);
			d++;
			cl = max(l, cl - 1);
			cr = min(r, cr + 1);
		}
	};

	check(s);

	return ans + 2 * sec;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~
books.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~

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