Submission #289571

#	Time	Username	Problem	Language	Result	Execution time	Memory
289571		eohomegrownapps	Ancient Books (IOI17_books)	C++14	0 / 100	1 ms	384 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> cycle;
vector<int> p;
ll n;

ll minc = 1e9;
ll maxc = -1e9;

struct UFDS{
	int n;
	vector<int> parent;
	UFDS(int _n){
		n = _n;
		parent.resize(n);
		for (int i = 0; i<n; i++){
			parent[i]=i;
		}
	}

	int root(int i){
		if (parent[i]==i){return i;}
		return parent[i]=root(parent[i]);
	}

	void connect(int a, int b){
		int ra = root(a);
		int rb = root(b);
		if (ra==rb){return;}
		parent[ra]=rb;
	}

	bool connected(int a, int b){
		return root(a) == root(b);
	}
};

ll findcycle(ll i, ll ptr){
	cycle[i] = ptr;
	minc=min(minc,i);
	maxc=max(maxc,i);
	if (cycle[p[i]]!=-1){
		return abs(i-p[i]);
	} else {
		return abs(i-p[i]) + findcycle(p[i], ptr);
	}
}

ll minimum_walk(std::vector<int> px, int s) {
	p = px;
	n = p.size();
	cycle.resize(n,-1);

	ll cycledist = 0;
	ll ptr = 0;

	vector<pair<int,int>> cycleranges;
	vector<ll> cyclewidth(n+1);
	ll minv = 1e9;
	ll maxv = -1e9;
	for (ll i = 0; i<n; i++){
		if (cycle[i]!=-1){continue;}
		minc=1e9;maxc=-1e9;
		ll dist = findcycle(i,ptr);
		//if (dist!=0){
			minv=min(minv,minc);
			maxv=max(maxv,maxc);
		//}
		cycleranges.push_back({minc,maxc});
		cyclewidth[minc]++;
		cyclewidth[maxc]--;
		cycledist+=dist;
		ptr++;
	}

	ll prev = 0;
	bool iszero = true;
	ll ctr = 0;
	ll minabove=1e9;
	ll maxbelow=-1e9;
	bool isbetween = false;
	for (ll i = 0; i<=n; i++){
		ctr+=cyclewidth[i];
		if (ctr==0&&i==s){
			isbetween=true;
		}
		if (iszero&&ctr>0){
			if (i<=s){
				maxbelow=max(maxbelow,i);
			}
			if (i>=s){
				minabove=min(minabove,i);
			}
			if (prev!=0){cycledist+=2*(i-prev);}
			iszero = false;
		} else if ((!iszero)&&ctr==0){
			if (i-1<=s){
				maxbelow=max(maxbelow,i-1);
			}
			if (i-1>=s){
				minabove=min(minabove,i-1);
			}
			prev = i;
			iszero = true;
		}
	}
	//cout<<maxbelow<<' '<<minabove<<endl;
	if (maxbelow==-1e9&&minabove==1e9){
		return 0;
	} else if (s<=minv||s>=maxv){
		return cycledist+2*min(minv-s,maxv-s);
	} else if (!isbetween){
		UFDS u(cycleranges.size());
		for (int i = 0; i<cycleranges.size()-1; i++){
			for (int j = i+1; j<cycleranges.size(); j++){
				int as = cycleranges[i].first;
				int ae = cycleranges[i].second;
				int bs = cycleranges[j].first;
				int be = cycleranges[j].second;
				if ((as<=bs&&bs<=ae&&bs<=ae&&ae<=be)||(bs<=as&&as<=be&&as<=be&&be<=ae)){
					u.connect(i,j);
				}
			}
		}
		vector<pair<int,int>> ranges(cycleranges.size(),{1e9,-1e9});
		for (int i = 0; i<cycleranges.size(); i++){
			int r = u.root(i);
			ranges[r].first=min(ranges[r].first,cycleranges[r].first);
			ranges[r].second=max(ranges[r].second,cycleranges[r].second);
		}
		vector<pair<int,int>> intersectingranges;
		for (auto p : ranges){
			if (p.first==1e9){continue;}
			if (p.first<=s&&s<=p.second){
				intersectingranges.push_back(p);
			}
		}
		sort(intersectingranges.begin(),intersectingranges.end());
		for (auto p : intersectingranges){
			cout<<p.first<<' '<<p.second<<endl;
		}
		ll dist = 0;
		for (int i = 0; i<intersectingranges.size()-1; i++){
			dist+=min(abs(intersectingranges[i+1].first-intersectingranges[i].first),
				abs(intersectingranges[i].second-intersectingranges[i+1].second));
		}
		//cout<<dist<<endl;
		cycledist+=2*dist;
	}
	return cycledist;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for (int i = 0; i<cycleranges.size()-1; i++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~
books.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for (int j = i+1; j<cycleranges.size(); j++){
      |                      ~^~~~~~~~~~~~~~~~~~~
books.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for (int i = 0; i<cycleranges.size(); i++){
      |                   ~^~~~~~~~~~~~~~~~~~~
books.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |   for (int i = 0; i<intersectingranges.size()-1; i++){
      |                   ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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