Submission #169971

#	Time	Username	Problem	Language	Result	Execution time	Memory
169971		dennisstar	Ancient Books (IOI17_books)	C++11	50 / 100	259 ms	45908 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

int n; vim P;
int fr, re;
ll ret;


vector<pii> im, ar, fin;

ll minimum_walk(vim p, int s) {
	n=p.size();

	for (fr=0; fr<n&&p[fr]==fr; fr++) {}
	for (re=n-1; re>=0&&p[re]==re; re--) {}
	for (int i=0; i<n; i++) ret+=abs(p[i]-i);
	if (!ret) return 0;

	vim chk(1000010);
	int mx;
	for (int i=fr; i<=re; i++) {
		if (chk[i]) continue;
		mx=0;
		for (int j=i; !chk[j]; j=p[j]) {
			chk[j]=1;
			mx=max(mx, j);
		}
		im.push_back({i, mx});
	}
	sort(im.begin(), im.end());

	for (int i=0; i<im.size(); i++) {
		int j;
		for (j=i+1; j<im.size()&&im[j].fi<=im[i].se; j++) im[i].se=max(im[i].se, im[j].se);
		i=j-1;
	}
	mx=-1;
	for (int i=0; i<im.size(); i++) {
		if (mx>=im[i].se) continue;
		mx=im[i].se;
		ar.push_back(im[i]);
	}

	
	for (int i=0; i<ar.size(); i++) {
		fin.push_back({ar[i].fi, i});
		fin.push_back({ar[i].se, i});
	}
	sort(fin.begin(), fin.end());
	int l;
	ll an1=0, an2=0;
	for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break;


	an1=abs(fin[l].fi-s)*2;
	for (int i=fin[l].se; i<ar.size()-1; i++) an1+=abs(ar[i+1].fi-ar[i].se)*2;
	//for (int i=fin[l].se; i>0; i--) an1+=abs(ar[i].fi-ar[i-1].se);
	
	if (l==0) return an1+ret;

	an2=abs(fin[l-1].se-s)*2;
	for (int i=fin[l-1].se; i>0; i--) an2+=abs(ar[i].fi-ar[i-1].se);
	for (int i=fin[l-1].se; i<ar.size()-1; i++) an2+=abs(ar[i+1].fi-ar[i].se)*2;

	return min(an1, an2)+ret;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(vim, int)':
books.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<im.size(); i++) {
                ~^~~~~~~~~~
books.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j=i+1; j<im.size()&&im[j].fi<=im[i].se; j++) im[i].se=max(im[i].se, im[j].se);
               ~^~~~~~~~~~
books.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<im.size(); i++) {
                ~^~~~~~~~~~
books.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ar.size(); i++) {
                ~^~~~~~~~~~
books.cpp:61:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (l=0; l<fin.size(); l++) if (fin[l].fi>=s) break;
            ~^~~~~~~~~~~
books.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=fin[l].se; i<ar.size()-1; i++) an1+=abs(ar[i+1].fi-ar[i].se)*2;
                        ~^~~~~~~~~~~~
books.cpp:72:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=fin[l-1].se; i<ar.size()-1; i++) an2+=abs(ar[i+1].fi-ar[i].se)*2;
                          ~^~~~~~~~~~~~

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