Submission #137096

#	Time	Username	Problem	Language	Result	Execution time	Memory
137096		baluteshih	Ancient Books (IOI17_books)	C++14	50 / 100	312 ms	22520 KiB

books

#include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int boss[1000005],mx[1000005],mi[1000005];

int finds(int x)
{
	if(boss[x]==x) return x;
	return boss[x]=finds(boss[x]);
}

void Union(int a,int b)
{
	a=finds(a),b=finds(b);
	boss[a]=b,mx[b]=max(mx[b],mx[a]),mi[b]=min(mi[b],mi[a]);
}

long long minimum_walk(vector<int> p, int s) 
{
	ll ans=0,ls=-1,L=0,R=0;
	for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
	for(int i=s;p[i]==i;++i)
		++R;
	if(R==p.size()-s) R=-1;
	for(int i=s;p[i]==i;--i)
		++L;
	if(L==s+1) L=-1;
	for(int i=0;i<p.size();++i)
		Union(i,p[i]);
	for(int i=0;i<p.size();++i)
		ans+=abs(p[i]-i);
	if(ans==0) return 0;
	for(int i=0;i<p.size();)
		if(finds(i),mx[boss[i]]==mi[boss[i]]) ++i;
		else
		{
			if(~ls) ans+=(mi[boss[i]]-ls)*2;
			for(ls=i;i<=mx[finds(ls)];++i)
				Union(ls,i);
			ls=i-1;
		}
	finds(s);
	if(mi[boss[s]]==mx[boss[s]])
		if(!~L) ans+=R*2;
		else if(!~R) ans+=L*2;
		else;
	else
		ans+=min(L*2,R*2);
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();++i) boss[i]=i,mx[i]=i,mi[i]=i;
              ~^~~~~~~~~
books.cpp:38:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(R==p.size()-s) R=-1;
     ~^~~~~~~~~~~~
books.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();++i)
              ~^~~~~~~~~
books.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();++i)
              ~^~~~~~~~~
books.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();)
              ~^~~~~~~~~

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