Submission #147834

#	Time	Username	Problem	Language	Result	Execution time	Memory
147834		faremy	Ancient Books (IOI17_books)	C++14	50 / 100	195 ms	26568 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;
bool gonnaCheck[MAXN];


void processcycle(int cycle, int &left, int &right)
{
	gonnaCheck[cycle] = true;
	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;
	}
}

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 left = s, right = s;
	int endLeft = 0, endRight = tables;

	processcycle(belongsTo[s], left, right);
	while (endLeft < left && cycInter[belongsTo[endLeft]].second - cycInter[belongsTo[endLeft]].first == 1)
		endLeft++;
	while (endRight > right && cycInter[belongsTo[endRight - 1]].second - cycInter[belongsTo[endRight - 1]].first == 1)
		endRight--;

	do {
		while (!toCheck.empty())
		{
			std::pair<int, int> checkingInter = toCheck.front();
			toCheck.pop();

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

		minWalk += 2;
		if (left != endLeft)
			processcycle(belongsTo[left - 1], left, right);
		else if (right != endRight)
			processcycle(belongsTo[right], left, right);
		else
			minWalk -= 2;
	} while (left != endLeft || right != endRight);

	return minWalk;
}

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