oj.uz

Submission #765960

# Submission time Handle Problem Language Result Execution time Memory
765960 2023-06-25T08:15:54 Z boris_mihov Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 340 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Incorrect 1 ms 308 KB 3rd lines differ - on the 1st token, expected: '5920', found: '5922'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -