oj.uz

Submission #758715

# Submission time Handle Problem Language Result Execution time Memory
758715 2023-06-15T07:58:27 Z boris_mihov Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 212 KB 
#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 < pos)
                    {
                        bool thereIsGood = false;;
                        for (int j = pos + 1 ; j <= r ; ++j)
                        {
                            if (p[j] > j)
                            {
                                thereIsGood = true;
                                break;
                            }
                        }

                        if (!thereIsGood)
                        {
                            break;
                        }
                    }
                }

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

                pos++;
                ans++;
            }
        } else
        {
            while (pos >= l)
            {
                if (pos == holding)
                {
                    std::swap(p[pos], holding);
                    if (holding > pos)
                    {
                        bool thereIsGood = false;;
                        for (int j = l ; j <= pos - 1 ; ++j)
                        {
                            if (p[j] < j)
                            {
                                thereIsGood = true;
                                break;
                            }
                        }

                        if (!thereIsGood)
                        {
                            break;
                        }
                    }
                }

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

                pos--;
                ans++;
            }
        }

        start ^= 1;
    }

	return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '3304', found: '6298'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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