Submission #1030400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030400		vjudge1	Ancient Books (IOI17_books)	C++17	50 / 100	98 ms	23516 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

long long minimum_walk(std::vector<int> p, int s) {
	int n=p.size();
	vector<int> vis(n,0);
	ll ans=0;
	vector<pair<int,int>> seg;
	rep(i,n){
		if(vis[i])continue;
		if(p[i]==i&&i!=s)continue;
		int lf=i;
		int ri=i;
		int pos=i;
		while(!vis[p[pos]]){
			ans+=abs(pos-p[pos]);
			pos=p[pos];
			vis[pos]=1;
			lf=min(lf,pos);
			ri=max(ri,pos);
		}
		seg.emplace_back(lf,ri);
	}
	sort(all(seg));
	vector<pair<int,int>> re={seg[0]};
	rng(i,1,seg.size()){
		if(seg[i].first<=re.back().second){
			re.back().second=max(re.back().second,seg[i].second);
		}
		else{
			re.emplace_back(seg[i]);
		}
	}
	rep(i,re.size()-1){
		ans+=2*(re[i+1].first-re[i].second);
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
      |                                    ^
books.cpp:31:2: note: in expansion of macro 'rng'
   31 |  rng(i,1,seg.size()){
      |  ^~~
books.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
books.cpp:39:2: note: in expansion of macro 'rep'
   39 |  rep(i,re.size()-1){
      |  ^~~

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