Submission #804854

#	Time	Username	Problem	Language	Result	Execution time	Memory
804854		Ellinor	Ancient Books (IOI17_books)	C++14	50 / 100	99 ms	20956 KiB

books

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

#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;


#include "books.h"

long long minimum_walk(std::vector<int> p, int s) 
{
	int cycles = 0;
	vector<int> cycle(p.size(), -1);
	vector<pii> lohi;

	ll base = 0;

	rep(i,0,p.size())
	{
		if (p[i] == i) cycle[i] = -1;
		else if (cycle[i] == -1)
		{
			cycle[i] = cycles;

			base += abs(i - p[i]);

			int at = p[i], low = i, high = i;
			while (at != i)
			{
				if (at < low) low = at;
				if (at > high) high = at;

				base += abs(at - p[at]);

				cycle[at] = cycles;
				at = p[at];
			}

			lohi.pb(make_pair(low, high));

			cycles++;
		}
	}

	ll add = 0;

	if (s == 0)
	{
		int low = 0, high = 0; // inc
		int ind = 0;
		rep(i,0,cycle.size())
		{
			if (cycle[i] == -1) continue;

			if (i > high) add += (i - high) * 2;
			high = max(high, lohi[cycle[i]].second);
		}
	}

	ll ans = base + add;

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:20:2: note: in expansion of macro 'rep'
   20 |  rep(i,0,p.size())
      |  ^~~
books.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:53:3: note: in expansion of macro 'rep'
   53 |   rep(i,0,cycle.size())
      |   ^~~
books.cpp:51:7: warning: unused variable 'low' [-Wunused-variable]
   51 |   int low = 0, high = 0; // inc
      |       ^~~
books.cpp:52:7: warning: unused variable 'ind' [-Wunused-variable]
   52 |   int ind = 0;
      |       ^~~

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