Submission #765982

#	Time	Username	Problem	Language	Result	Execution time	Memory
765982		boris_mihov	Ancient Books (IOI17_books)	C++17	100 / 100	122 ms	31476 KiB

books

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

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

int n, s;
int p[MAXN];
int add[MAXN];
bool vis[MAXN];
int lCycle[MAXN];
int rCycle[MAXN];
int inCycle[MAXN];

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

    int max = 0;
    int cnt = 0;
    int neededL = s;
    int neededR = s;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (vis[i])
        {
            continue;
        }

        cnt++;
        int curr = i;
        lCycle[cnt] = rCycle[cnt] = i;
        while (!vis[curr])
        {
            vis[curr] = true;
            inCycle[curr] = cnt;
            lCycle[cnt] = std::min(lCycle[cnt], curr);
            rCycle[cnt] = std::max(rCycle[cnt], curr);
            curr = p[curr];
        }

        if (curr != p[curr])
        {
            neededL = std::min(neededL, lCycle[cnt]);
            neededR = std::max(neededR, rCycle[cnt]);
        }
    }

    int myL = s;
    int myR = s;
    int ptrL = lCycle[inCycle[s]];
    int ptrR = rCycle[inCycle[s]];

    while (true)
    {
        while (true)
        {
            while (myL >= ptrL)
            {
                ptrL = std::min(ptrL, lCycle[inCycle[myL]]);
                ptrR = std::max(ptrR, rCycle[inCycle[myL]]);
                myL--;
            }

            while (myR <= ptrR)
            {
                ptrL = std::min(ptrL, lCycle[inCycle[myR]]);
                ptrR = std::max(ptrR, rCycle[inCycle[myR]]);
                myR++;
            }

            if (ptrL == myL + 1 && ptrR == myR - 1)
            {
                myL++;
                myR--;
                break;
            }
        }

        if (myL == neededL && myR == neededR)
        {
            break;
        }
        
        int addL = 0;
        int addR = 0;
        int nextL = myL - 1;
        int nextR = myR + 1;
        int ptrNextL = myL; 
        int ptrNextR = myR;
        int min, max; 

        max = 0;
        while (ptrNextL > neededL)
        {
            addL += 2;
            ptrNextL--;
            while (nextL >= ptrNextL)
            {
                max = std::max(max, rCycle[inCycle[nextL]]);
                ptrNextL = std::min(ptrNextL, lCycle[inCycle[nextL]]);
                nextL--;
            }

            if (max >= s)
            {
                break;
            }
        }

        min = n + 1;
        while (ptrNextR < neededR)
        {
            addR += 2;
            ptrNextR++;
            while (nextR <= ptrNextR)
            {
                min = std::min(min, lCycle[inCycle[nextR]]);
                ptrNextR = std::max(ptrNextR, rCycle[inCycle[nextR]]);
                nextR++;
            }

            if (min <= s)
            {
                break;
            }
        }

        if (max < s)
        {
            ans += addL;
            ans += addR;
            break;
        }

        ans += std::min(addL, addR);
        ptrL = ptrNextL;
        ptrR = ptrNextR;
    }

	return ans;
}

Compilation message (stderr)

books.cpp: In function 'llong minimum_walk(std::vector<int>, int)':
books.cpp:29:9: warning: unused variable 'max' [-Wunused-variable]
   29 |     int max = 0;
      |         ^~~

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