Submission #758727

#	Time	Username	Problem	Language	Result	Execution time	Memory
758727		boris_mihov	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	212 KiB

books

#include "books.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, s;
int p[MAXN];
int pointingTo[MAXN];
llong ans;

bool notSorted()
{
    for (int i = 1 ; i < n ; ++i)
    {
        if (p[i] > p[i + 1])
        {
            return true;
        }
    }

    return false;
}

llong minimum_walk(std::vector <int> P, int S) 
{
    n = P.size(); s = S + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        p[i] = P[i - 1] + 1;
    }

    int pos = s;
    int holding = -1;
    bool start = false;
    int l = 1, r = n;

    while (true)
    {
        while (l <= r && p[l] == l)
        {
            l++;
        }

        while (l <= r && p[r] == r)
        {
            r--;
        }

        if (l > r)
        {
            break;
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            pointingTo[p[i]] = i;
        }

        if (!start)
        {
            while (pos <= r)
            {
                if (pos == holding)
                {
                    std::swap(p[pos], holding);
                    if (holding == -1 || holding < pos)
                    {
                        break;
                    }
                }

                if (p[pos] > pos && (holding == -1 || p[pos] < holding))
                {
                    std::swap(holding, p[pos]);
                }

                pos++;
                ans++;
            }

            if (pos > r)
            {
                pos--;
                ans--;
            }
        } else
        {
            while (pos >= l)
            {
                if (pos == holding)
                {
                    std::swap(p[pos], holding);
                    if (holding == -1 || holding > pos)
                    {
                        break;
                    }
                }

                if (p[pos] < pos && (holding == -1 || p[pos] > holding))
                {
                    std::swap(holding, p[pos]);
                }

                pos--;
                ans++;
            }

            if (pos < l)
            {
                pos++;
                ans--;
            }
        }

        start ^= 1;
    }

    ans += abs(pos - s);
	return ans;
}

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