제출 #464907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464907		blue	고대 책들 (IOI17_books)	C++17	50 / 100	192 ms	23820 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_new <= l-1 || r+1 <= r_new)
	{
		if(l_new <= l-1)
		{
			l--;
			l_new = min(l_new, L[cycle[l]]);
			r_new = max(r_new, R[cycle[l]]);
		}

		if(r+1 <= 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)
	{
		extend(l, r);

		int new_l = -1, new_r = -1;
		int left_cost, right_cost;
		for(int i = l-1; i >= solve_L; i--)
		{
			if(P[i] != i)
			{
				new_l = i;
				left_cost = 2*(l - new_l);
				break;
			}
		}
		for(int i = r+1; i <= solve_R; i++)
		{
			if(P[i] != i)
			{
				new_r = i;
				right_cost = 2*(new_r - r);
				break;
			}
		}

		if(new_l != -1 && new_r != -1)
		{
			int l1 = l, r1 = r;
			extend(new_l, r1);
			extend(l1, new_r);

			// if((S <= R[ cycle[new_l] ]) != (L[ cycle[new_r] ] <= S))
			// 	while(1);

			if(S <= r1) //&& L[ cycle[new_r] ] <= S
			{
				extra_cost += min(left_cost, right_cost);
			}
			else
			{
				extra_cost += left_cost + right_cost;
			}

			l = new_l;
			r = new_r;
			extend(l, r);
		}
		else if(new_l != -1)
		{
			extra_cost += 2*(l - new_l);
			l = new_l;
			extend(l, r);
		}
		else if(new_r != -1)
		{
			extra_cost += 2*(new_r - r);
			r = new_r;
			extend(l, r);
		}
		else break;
	}

	return essential_cost + extra_cost;
}

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