Submission #134719

#	Time	Username	Problem	Language	Result	Execution time	Memory
134719		dvdg6566	Ancient Books (IOI17_books)	C++14	50 / 100	239 ms	22904 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1001000
typedef long long ll;


ll done[MAXN];
ll N,ans;
ll lst;

long long minimum_walk(std::vector<int> p, int s) {
	assert(s==0);
	N=p.size();
	ll pp = 0;
	for (int i=0;i<N;++i){
		if (done[i])continue;
		if (p[i]==i)continue;
		done[i]=1;
		ll x = p[i];
		ans += p[i] - i;
		if (i > lst)ans += (i-lst)*2;

		while (x!=i){
			lst = max(lst,x);
			done[x] = 1;
			ans += abs(p[x] - x);
			x = p[x];
		}
		// cout<<lst<<'\n';
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:15:5: warning: unused variable 'pp' [-Wunused-variable]
  ll pp = 0;
     ^~

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