Submission #805051

#	Time	Username	Problem	Language	Result	Execution time	Memory
805051		Ellinor	Ancient Books (IOI17_books)	C++14	50 / 100	105 ms	14188 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) 
{
	cerr << "hi " << s << "\n";

	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);
		}
	}

	else
	{
		cerr << "else\n";

		vector<int> closest(cycle.size(), -1);

		if (cycle[0] == -1) closest[0] = -1;
		else closest[0] = 0;

		rep(i,1,s)
		{
			if (cycle[i] == -1) closest[i] = closest[i - 1];
			else closest[i] = i;
		}

		if (cycle[cycle.size() - 1] == -1) closest[cycle.size() - 1] = -1;
		else closest[cycle.size() - 1] = cycle.size() - 1;

		for (int i = cycle.size() - 2; i > s; i--) // -2 !!
		{
			if (cycle[i] == -1) closest[i] = closest[i + 1];
			else closest[i] = i;
		}

		cerr << "closest: ";
		rep(i,0,closest.size())
		{
			cerr << closest[i] << " ";
		}
		cerr << "\n";

		// edges

		int low = s, high = s;
		if (cycle[s] != -1)
		{
			low = lohi[cycle[s]].first;
			high = lohi[cycle[s]].second;
		}

		while (low > 0 || high < cycle.size() - 1)
		{
			int go;

			if (low > 0 && high < cycle.size() - 1)
			{
				if (closest[low - 1] == -1) 
				{
					low = 0;
					continue;
				}
				if (closest[high + 1] == -1)
				{
					high = cycle.size() - 1;
					continue;
				}

				if (low - closest[low - 1] < closest[high + 1] - high) 
				{
					go = closest[low - 1];
					add += (low - closest[low - 1]) * 2;
				}
				else 
				{
					go = closest[high + 1];
					add += (closest[high + 1] - high) * 2;
				}
			}

			else if (high < cycle.size() - 1)
			{
				if (closest[high + 1] == -1)
				{
					high = cycle.size() - 1;
					continue;
				}

				go = closest[high + 1];
				add += (closest[high + 1] - high) * 2;
			}

			else // low > 0
			{
				if (closest[low - 1] == -1) 
				{
					low = 0;
					continue;
				}

				go = closest[low - 1];
				add += (low - closest[low - 1]) * 2;

				cerr << "add add " << low << " " << closest[low - 1] << " " << (low - closest[low - 1]) * 2 << "\n";
			}


			low = min(low, lohi[cycle[go]].first);
			high = max(high, lohi[cycle[go]].second);
		}
	}

	ll ans = base + add;

	cerr << ans << "\n";

	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:22:2: note: in expansion of macro 'rep'
   22 |  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:55:3: note: in expansion of macro 'rep'
   55 |   rep(i,0,cycle.size())
      |   ^~~
books.cpp:53:7: warning: unused variable 'low' [-Wunused-variable]
   53 |   int low = 0, high = 0; // inc
      |       ^~~
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:89:3: note: in expansion of macro 'rep'
   89 |   rep(i,0,closest.size())
      |   ^~~
books.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   while (low > 0 || high < cycle.size() - 1)
      |                     ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    if (low > 0 && high < cycle.size() - 1)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    else if (high < cycle.size() - 1)
      |             ~~~~~^~~~~~~~~~~~~~~~~~

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