Submission #423825

#	Time	Username	Problem	Language	Result	Execution time	Memory
423825		Bill_00	Ancient Books (IOI17_books)	C++14	50 / 100	230 ms	23748 KiB

books

#include "books.h"
#include  <bits/stdc++.h>
#define ll long long
using namespace std;
ll p[1000005],ans,vis[1000005],mx,mn;
void dfs(ll node){
	ans+=(abs(node-p[node]));
	vis[node]=1;
	mx=max(node,mx);
	mn=min(node,mn);
	if(vis[p[node]]) return;
	dfs(p[node]);
}
long long minimum_walk(std::vector<int> P, int s){
	for(ll i=0;i<P.size();i++) p[i]=P[i];
	for(ll i=0;i<P.size();i++){
		if(vis[i]==0 && i!=p[i]){
			if(i>mx){
				ans+=((i-mx)*2);
				mn=i;
			}
			dfs(i);
			if(mn<=s && s<=mx){
				ans+=(min(s-mn,mx-s)*2);
			}
		}
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:15:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(ll i=0;i<P.size();i++) p[i]=P[i];
      |             ~^~~~~~~~~
books.cpp:16:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(ll i=0;i<P.size();i++){
      |             ~^~~~~~~~~

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