Submission #147836

#	Time	Username	Problem	Language	Result	Execution time	Memory
147836		faremy	Ancient Books (IOI17_books)	C++14	50 / 100	198 ms	20472 KiB

books

#include "books.h"

#include <cstdlib>
#include <queue>
#include <utility>


const int MAXN = 1e6;

int belongsTo[MAXN];
std::pair<int, int> cycInter[MAXN];
std::queue<std::pair<int, int>> toCheck;


void processcycle(int cycle, int &left, int &right)
{
	if (cycInter[cycle].first < left)
	{
		toCheck.emplace(cycInter[cycle].first, left);
		left = cycInter[cycle].first;
	}
	
	if (cycInter[cycle].second > right)
	{
		toCheck.emplace(right, cycInter[cycle].second);
		right = cycInter[cycle].second;
	}
}

std::pair<int, int> check(int doneLeft, int doneRight)
{
	int left = doneLeft, right = doneRight;
	while (!toCheck.empty())
	{
		std::pair<int, int> checkingInter = toCheck.front();
		toCheck.pop();

		for (int iTable = checkingInter.first; iTable < checkingInter.second; iTable++)
			processcycle(belongsTo[iTable], left, right);
	}

	return { left, right };
}

long long minimum_walk(std::vector<int> p, int s)
{
	int tables = p.size();
	std::fill_n(belongsTo, tables, -1);
	long long minWalk = 0;

	int cycles = 0;
	for (int iTable = 0; iTable < tables; iTable++)
		if (belongsTo[iTable] == -1)
		{
			int leftMost = tables, rightMost = 0;
			int curTable = iTable;

			while (belongsTo[curTable] == -1)
			{
				leftMost = std::min(leftMost, curTable);
				rightMost = std::max(rightMost, curTable);

				belongsTo[curTable] = cycles;
				minWalk += (long long)std::abs(curTable - p[curTable]);
				curTable = p[curTable];
			}

			cycInter[cycles] = { leftMost, rightMost + 1 };
			cycles++;
		}

	int endLeft = 0, endRight = tables;
	while (endLeft < s && cycInter[belongsTo[endLeft]].second - cycInter[belongsTo[endLeft]].first == 1)
		endLeft++;
	while (endRight - 1 > s && cycInter[belongsTo[endRight - 1]].second - cycInter[belongsTo[endRight - 1]].first == 1)
		endRight--;

	toCheck.emplace(s, s + 1);
	std::pair<int, int> done = check(s, s + 1);

	while (done.first != endLeft || done.second != endRight)
	{
		long long costLeft = 0;
		std::pair<int, int> moveLeft = done;

		while (moveLeft.first != endLeft && moveLeft.second == done.second)
		{
			toCheck.emplace(moveLeft.first - 1, moveLeft.first);
			costLeft += 2;
			moveLeft = check(moveLeft.first - 1, moveLeft.second);
		}

		long long costRight = 0;
		std::pair<int, int> moveRight = done;

		while (moveRight.first == done.first && moveRight.second != endRight)
		{
			toCheck.emplace(moveRight.second, moveRight.second + 1);
			costRight += 2;
			moveRight = check(moveRight.first, moveRight.second + 1);
		}

		if (moveLeft == moveRight)
		{
			minWalk += std::min(costLeft, costRight);
			done = { endLeft, endRight };
		}
		else
		{
			minWalk += costLeft + costRight;
			done = { endLeft, endRight };
		}
	}

	return minWalk;
}

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