제출 #765960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765960		boris_mihov	고대 책들 (IOI17_books)	C++17	0 / 100	1 ms	340 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;
    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];
        }
    }

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

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

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

        if (myL == 1 && myR == n)
        {
            break;
        }

        int addL = (myL > 1) * 2;
        int addR = (myR < n) * 2;
        int nextL = myL - 1;
        int nextR = myR + 1;
        int ptrNextL = myL - 1; 
        int ptrNextR = myR + 1;
        int min, max; 

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

            if (max >= s)
            {
                break;
            }

            if (nextL > 1)
            {
                addL += 2;
                ptrNextL--;
            }
        }

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

            if (min <= s)
            {
                break;
            }

            if (nextR < n)
            {
                addR += 2;
                ptrNextR++;
            }
        }

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

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

	return ans;
}

컴파일 시 표준 에러 (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: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30