Submission #464909

#	Time	Username	Problem	Language	Result	Execution time	Memory
464909		blue	Ancient Books (IOI17_books)	C++17	0 / 100	37 ms	19860 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';

    long long dp[1000][1000];
    dp[solve_L][solve_R] = 0;
    for(int delta = solve_R - solve_L; delta >= 0; delta--)
    {
        for(int lx = solve_L; lx + delta <= solve_R; lx++)
        {
            int rx = lx + delta;
            if(lx == solve_L && rx == solve_R)
            {
                dp[lx][rx] = 0;
                continue;
            }

            dp[lx][rx] = INF;

            int l, r;

            l = lx-1;
            r = rx;
            if(solve_L <= l)
            {
                extend(l, r);
                dp[lx][rx] = min(dp[lx][rx], dp[l][r] + 2);
            }

            l = lx;
            r = rx+1;
            if(r <= solve_R)
            {
                extend(l, r);
                dp[lx][rx] = min(dp[lx][rx], dp[l][r] + 2);
            }
        }
    }

	// 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 += left_cost;
	// 		l = new_l;
	// 		extend(l, r);
	// 	}
	// 	else if(new_r != -1)
	// 	{
	// 		extra_cost += right_cost;
	// 		r = new_r;
	// 		extend(l, r);
	// 	}
	// 	else break;
	// }

	return essential_cost + dp[S][S];
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:95:12: warning: unused variable 'extra_cost' [-Wunused-variable]
   95 |  long long extra_cost = 0;
      |            ^~~~~~~~~~

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