Submission #1225385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225385		Malix	Ancient Books (IOI17_books)	C++20	50 / 100	187 ms	43644 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi a,vis,arr;

void dfs(int x){
	arr.PB(x);
	vis[x]=1;
	if(vis[a[x]]==0)dfs(a[x]);
}

long long minimum_walk(std::vector<int> p, int s) {
	a=p;
	int n=a.size();
	vis.resize(n,0);
	vector<pi> b;
	int pos=0;
	while(pos<n&&a[pos]==pos)pos++;
	if(pos==n)return 0;
	ll ans=(ll)pos*2LL;
	REP(i,pos,n)if(!vis[i]&&i!=a[i]){
		arr.clear();
		dfs(i);
		sort(all(arr));
		for(auto u:arr)ans+=(ll)abs(u-a[u]);
		b.PB({arr[0],arr.back()});
	}
	sort(all(b));
	int mx=b[0].S;
	REP(i,1,b.size()){
		if(b[i].F>mx)ans+=(ll)(b[i].F-mx)*2LL;
		mx=max(mx,b[i].S);
	}
	return ans;
}

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