Submission #309849

#	Time	Username	Problem	Language	Result	Execution time	Memory
309849		CaroLinda	Ancient Books (IOI17_books)	C++14	22 / 100	2036 ms	23868 KiB

books

#include "books.h"
#include <bits/stdc++.h>
 
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
 
const int MAX = 1e6+10 ;
const ll inf = 1e18+10 ;
 
using namespace std ;
 
//Tentando uma ideia (provavelmente vai dar errado mas vamos nessa)

vector<pii> intervalo ;
int n , L , R ;
int dist[MAX] ;

void bfs(int inicio)
{

	int l = inicio , r = inicio ;

	priority_queue<pii, vector<pii> , greater<pii> > fila ;
	fila.push(make_pair(0,inicio)) ;

	lp(i,0,n) dist[i] = n+5;
	dist[inicio] = 0 ;

	while(!fila.empty())
	{
		int x = fila.top().ss ;
		int d = fila.top().ff ;
		fila.pop() ;

		if(d != dist[x]) continue ;

		l = min(l, intervalo[x].ff );
		r = max(r, intervalo[x].ss ) ;

		vector<pii> adj ;
 
		if(x > L )
		{
			if( x-1 >= l && x <= r )
				adj.push_back(make_pair(x-1,0)) ;
			else adj.push_back(make_pair(x-1, 1)) ;
		}
		if(x+1 <= R )
		{
			if( x >= l && x+1 <= r )
				adj.push_back(make_pair(x+1, 0)); 
			else adj.push_back(make_pair(x+1, 1 ) ) ;
		}
 
		for(auto e : adj)
		{
			int y = e.ff ;
			int cost = e.ss ;
 
			if(dist[y]<= cost+dist[x]) continue ;
 
			dist[y] = dist[x]+cost ;
 
			fila.push(make_pair(dist[y] , y ));
 
		}

	}

}

long long minimum_walk(vector<int> p, int s) 
{
 
	n = sz(p) ;
	ll ans = 0LL ;
 
	lp(i,0,n) ans += (ll)(abs(p[i]-i)) ;
 
	L = 0  ;
	R = n-1 ;
 
	while(L < s && p[L] == L ) L++ ;
	while(R > s && p[R] == R) R-- ;
 
	vector<bool> vis( n, false ) ;
	intervalo.resize(n, make_pair(-1,-1) ) ;
 
	for(int i = L ; i <= R ; i++ )
	{
		if(vis[i]) continue ;
 
		vector<int> List ;
 
		int x = i , l = i , r = i;
		while(!vis[x])
		{
			vis[x] = true ;
			List.push_back(x) ;
			
			l = min(l,x) ;
			r = max(r,x) ;
 
			x = p[x] ;
		}
 
		for(auto e : List ) intervalo[e] = make_pair(l,r) ;
 
	}
 
	
	ll gordura = inf ;

	vector<int> distBase(n) ;
	bfs(s) ;

	lp(i,0,n) distBase[i] = dist[i] ;

	for(int i = L ; i <= R ; i++ )
	{
		bfs(i) ;
		gordura = min(gordura, (ll)distBase[i] + dist[L] + dist[R]) ;
	}

	return ans + 2LL*gordura ;

}

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