Submission #805190

#	Time	Username	Problem	Language	Result	Execution time	Memory
805190		Ellinor	Ancient Books (IOI17_books)	C++14	50 / 100	127 ms	14184 KiB

books

#include <bits/stdc++.h>
#include <unordered_map>
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);
		}
	}

	else
	{
		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--)
		{
			if (cycle[i] == -1) closest[i] = closest[i + 1];
			else closest[i] = i;
		}

		// edges

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

        //

        map<pii, ll> dp; // ??

        priority_queue<array<ll, 3>> pq;
        pq.push({-0, low, high});

        dp[make_pair(low, high)] = -1;

        while (!pq.empty())
        {
            auto x = pq.top();
            pq.pop();

            ll steps = x[0];
            steps = -steps;
            low = x[1];
            high = x[2];

            //

            int go = -1;

            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 > 0 && high < cycle.size() - 1)
			{
                int low1 = low, high1 = high, steps1 = steps;

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

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

                if (dp[make_pair(low1, high1)] == 0) 
                {
                    if (low1 == 0 && high1 == cycle.size() - 1) 
                    {
                        add = steps1;
                        break;
                    }

                    dp[make_pair(low1, high1)] = steps1;
                    pq.push({-steps1, low1, high1});
                }
                
                //

                low1 = low, high1 = high, steps1 = steps;

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

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

                if (dp[make_pair(low1, high1)] == 0 || steps1 < dp[make_pair(low1, high1)]) // dp[make_pair(low1, high1)] == 0
                {
                    if (low1 == 0 && high1 == cycle.size() - 1) 
                    {
                        add = steps1;
                        break;
                    }

                    dp[make_pair(low1, high1)] = steps1;
                    pq.push({-steps1, low1, high1});
                }
                
                continue;
			}

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

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

			else if (low > 0)
			{
				if (closest[low - 1] == -1) 
				{
					add = steps;
                    break;
				}

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

            if (go == -1)
            {
                add = steps;
                break;
            }


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

            //

            if (dp[make_pair(low, high)] != 0) continue; // ??
            dp[make_pair(low, high)] = steps;

            if (low == 0 && high == cycle.size() - 1) 
            {
                add = steps;
                break;
            }

            pq.push({-steps, low, high});
        }

        //
	}

	ll ans = base + add;

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:21:2: note: in expansion of macro 'rep'
   21 |  rep(i,0,p.size())
      |  ^~~
books.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for (int i = (a); i < (b); i++)
      |                                        ^
books.cpp:54:3: note: in expansion of macro 'rep'
   54 |   rep(i,0,cycle.size())
      |   ^~~
books.cpp:52:7: warning: unused variable 'low' [-Wunused-variable]
   52 |   int low = 0, high = 0; // inc
      |       ^~~
books.cpp:117:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             if (low > 0 && high < cycle.size() - 1)
      |                            ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if (low > 0 && high < cycle.size() - 1)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:143:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                     if (low1 == 0 && high1 == cycle.size() - 1)
      |                                      ~~~~~~^~~~~~~~~~~~~~~~~~~
books.cpp:165:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |                     if (low1 == 0 && high1 == cycle.size() - 1)
      |                                      ~~~~~~^~~~~~~~~~~~~~~~~~~
books.cpp:178:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |    else if (high < cycle.size() - 1)
      |             ~~~~~^~~~~~~~~~~~~~~~~~
books.cpp:217:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |             if (low == 0 && high == cycle.size() - 1)
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~

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