Submission #797465

#	Time	Username	Problem	Language	Result	Execution time	Memory
797465		firewater	Ancient Books (IOI17_books)	C++14	50 / 100	118 ms	27648 KiB

books

#include "books.h"
#include <cstdio>
#include <vector>
#include <cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1001000
#define mp make_pair
#define fs first
#define sn second
using namespace std;

ll n,m,w,x,y,s,ans,now,gg,to[N],mx[N],mi[N],fa[N],fr[N];
void dfs(ll x)
{
	if(fr[x])return;

	fr[x]=w;
	mx[w]=max(mx[w],x);
	mi[w]=min(mi[w],x);
	ans+=abs(x-to[x]);
	dfs(to[x]);
	return;
}
long long minimum_walk(std::vector<int> too, int ss) {
	n=too.size();
	for(ll i=1;i<=n;++i)
		to[i]=too[i-1]+1;
	s=ss+1;

	w=m=0;
	for(ll i=1;i<=n;++i)
		if(!fr[i]&&to[i]!=i){
			++w;
			mi[w]=1001000;
			mx[w]=0;
			dfs(i);
		}
	gg=n;
	while(gg>0&&(!fr[gg]))gg--;
	now=1;
	for(ll i=1;i<=gg;++i){
		if(now<i)now++,ans+=2;
		if(fr[i])now=max(now,mx[fr[i]]);
	}
	return ans;
}

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