Submission #169963

#	Time	Username	Problem	Language	Result	Execution time	Memory
169963		dennisstar	Ancient Books (IOI17_books)	C++11	12 / 100	8 ms	4344 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; im[j].fi<im[i].se; j++) im[i].se=max(im[i].se, im[j].se);
		i=j+1;
	}
	mx=-1;
	for (pii pi:im) {
		if (pi.se<=mx) continue;
		mx=pi.se;
		ar.push_back(pi);
	}
	
	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;

	int lst=s;
	fill(chk.begin(), chk.end(), 0);
	for (int i=l; i<fin.size(); i++) {
		if (chk[fin[i].se]) continue;
		chk[fin[i].se]=1;
		an1+=abs(fin[i].fi-lst);
		lst=fin[i].fi;
	}
	for (int i=l-1; i>=0; i--) {
		if (chk[fin[i].se]) continue;
		chk[fin[i].se]=1;
		an1+=abs(fin[i].fi-lst);
		lst=fin[i].fi;
	}
	an1+=abs(lst-s);
	
	lst=s;
	fill(chk.begin(), chk.end(), 0);
	for (int i=l-1; i>=0; i--) {
		if (chk[fin[i].se]) continue;
		chk[fin[i].se]=1;
		an2+=abs(fin[i].fi-lst);
		lst=fin[i].fi;
	}
	for (int i=l; i<fin.size(); i++) {
		if (chk[fin[i].se]) continue;
		chk[fin[i].se]=1;
		an2+=abs(fin[i].fi-lst);
		lst=fin[i].fi;
	}
	an2+=abs(lst-s);
	return min(an1, an2)+ret;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(vim, int)':
books.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<im.size(); i++) {
                ~^~~~~~~~~~
books.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<ar.size(); i++) {
                ~^~~~~~~~~~
books.cpp:59: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:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=l; i<fin.size(); i++) {
                ~^~~~~~~~~~~
books.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=l; i<fin.size(); i++) {
                ~^~~~~~~~~~~

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