Submission #464883

#	Time	Username	Problem	Language	Result	Execution time	Memory
464883		blue	Ancient Books (IOI17_books)	C++17	50 / 100	224 ms	30660 KiB

books

#include "books.h"
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxN = 1'000'000;

const int ind_R = 1'000'005;
const int ind_L = -1;

const long long INF = 1'000'000'000'000'000'000LL;

int N;
vector<int> P;

int S;

int cycle_ind = -1;
vector<int> cycle(maxN, -1);
vector<int> L(maxN, ind_R);
vector<int> R(maxN, ind_L);

long long essential_cost = 0;

void extend(int& l, int& r) //[l, r] is extended fully except for the cycles of l and r
{
	int l_new = min(L[cycle[l]], L[cycle[r]]);
	int r_new = max(R[cycle[l]], R[cycle[r]]);

	// cerr << "ln = " << l_new << ", rn = " << r_new << '\n';

	while(l != l_new || r != r_new)
	{
		if(l != l_new)
		{
			l--;
			l_new = min(l_new, L[cycle[l]]);
			r_new = max(r_new, R[cycle[l]]);
		}

		if(r != r_new)
		{
			r++;
			l_new = min(l_new, L[cycle[r]]);
			r_new = max(r_new, R[cycle[r]]);
		}
	}
}

long long minimum_walk(vector<int> p, int s)
{
	N = p.size();
	P = p;
	S = s;

	int solve_L = S;
	int solve_R = S;

	for(int i = 0; i < N; i++)
	{
		essential_cost += abs(P[i] - i);

		if(P[i] != i)
		{
			solve_L = min(solve_L, i);
			solve_R = max(solve_R, i);
		}

		if(cycle[i] != -1) continue;

		cycle_ind++;

		int j = i;
		do
		{
			cycle[j] = cycle_ind;

			L[ cycle[j] ] = min(L[ cycle[j] ], j);
			R[ cycle[j] ] = max(R[ cycle[j] ], j);

			j = P[j];
		} while(j != i);
	}

	if(solve_L == S && solve_R == S) return 0;

	// for(int i = 0; i < N; i++) cerr << cycle[i] << ' ';
	// cerr << '\n';
	//
	// cerr << "solve range = " <<  solve_L << ' ' << solve_R << '\n';


	long long extra_cost = 0;

	int l = S;
	int r = S;
	// cerr << "l = " << l << ", r = " << r << '\n';
	extend(l, r);
	// cerr << "l = " << l << ", r = " << r << '\n';

	while(l != solve_L || r != solve_R)
	{
		bool S_cycle_exists = 0;

		long long left_cost = 0;
		int new_l;
		for(int i = l-1; i >= solve_L; i--)
		{
			if(R[ cycle[i] ] >= S)
			{
				S_cycle_exists = 1;
				left_cost = 2*(l - i);
				new_l = i;
				break;
			}
		}

		if(!S_cycle_exists) break;

		long long right_cost = 0;
		int new_r;
		for(int i = r+1; i <= solve_R; i++)
		{
			if(L[ cycle[i] ] <= S)
			{
				right_cost = 2*(i - r);
				new_r = i;
				break;
			}
		}

		extra_cost += min(left_cost, right_cost);
		l = new_l;
		r = new_r;
		extend(l, r);
	}

	for(int l2 = l-1; l2 >= solve_L; l2--)
	{
		if(l2 >= l) continue;
		if(R[ cycle[l2] ] == l2)
		{
			extra_cost += 2*(l - l2);
			l = l2;
			extend(l, r);
		}
	}

	for(int r2 = r+1; r2 <= solve_R; r2++)
	{
		if(r2 <= r) continue;
		if(L[ cycle[r2] ] == r2)
		{
			extra_cost += 2*(r2 - r);
			r = r2;
			extend(l, r);
		}
	}

	return essential_cost + extra_cost;
}

Compilation message (stderr)

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

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