oj.uz

Submission #66465

# Submission time Handle Problem Language Result Execution time Memory
66465 2018-08-10T16:11:10 Z Kubalionzzale Gondola (IOI14_gondola) C++14
55 / 100
 68 ms 3708 KB 
#include "gondola.h"

#include <iostream>
#include <functional>
#include <algorithm>
#include <set>

int valid(int n, int a[])
{
    bool visited[250010] = { 0 };
    int remember = -1;
    for (int i = 0; i < n; ++i)
    {
        --a[i];
        if (visited[a[i]])
            return 0;
        else
            visited[a[i]] = 1;

        if (a[i] < n)
        {
            if (remember == -1)
                remember = i;
            else
            {
                int val1 = a[remember];
                int val2 = a[i];

                if (val1 > val2)
                {
                    if (remember == (i + (val1 - val2)) % n)
                        continue;
                    else
                        return 0;
                }
                else
                {
                    if (i == (remember + (val2 - val1)) % n)
                        continue;
                    else
                        return 0;
                }
            }
        }
    }

    return 1;
}

//----------------------

int replacement(int n, int a[], int ans[])
{
    int model[100010] = { 0 };
    std::set< std::pair<int, int>, std::greater< std::pair<int, int> > > set;
    int diff = 0;
    bool visited[250010] = { 0 };
    int max = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] <= n)
        {
            --a[i];

            diff = (i - a[i] + n) % n;

            ++a[i];
        }

        if (a[i] > n)
            set.insert(std::make_pair(a[i], i));

        visited[a[i]] = true;
        if (a[i] > max)
            max = a[i];
    }

    int lastunused = max - 1;
    while (visited[lastunused])
    {
        --lastunused;
    }

    if (max == n)
        return 0;
    int cnt = max - n;
    int returning = cnt;
    --cnt;

    while (set.empty() == false)
    {
        std::pair<int, int> cur = *set.begin();
        set.erase(set.begin());

        if (lastunused <= n)
        {
            ans[cnt] = ((cur.second - diff) + n) % n;
            ++ans[cnt];
            --cnt;
        }
        else
        {
            ans[cnt] = lastunused;
            --cnt;

            cur.first = lastunused;
            set.insert(cur);
            --lastunused;

            while (visited[lastunused])
            {
                --lastunused;
            }
        }
    }

    return returning;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:54:9: warning: unused variable 'model' [-Wunused-variable]
     int model[100010] = { 0 };
         ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 3 ms 756 KB Output is correct
5 Correct 2 ms 756 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 816 KB Output is correct
2 Correct 2 ms 868 KB Output is correct
3 Correct 2 ms 868 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 3 ms 868 KB Output is correct
6 Correct 8 ms 1168 KB Output is correct
7 Correct 14 ms 1496 KB Output is correct
8 Correct 12 ms 1496 KB Output is correct
9 Correct 6 ms 1496 KB Output is correct
10 Correct 14 ms 1496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1496 KB Output is correct
2 Correct 2 ms 1496 KB Output is correct
3 Correct 2 ms 1496 KB Output is correct
4 Correct 3 ms 1496 KB Output is correct
5 Correct 2 ms 1496 KB Output is correct
6 Correct 7 ms 1496 KB Output is correct
7 Correct 14 ms 1496 KB Output is correct
8 Correct 12 ms 1528 KB Output is correct
9 Correct 5 ms 1528 KB Output is correct
10 Correct 15 ms 1528 KB Output is correct
11 Correct 2 ms 1528 KB Output is correct
12 Correct 2 ms 1528 KB Output is correct
13 Correct 10 ms 1528 KB Output is correct
14 Correct 2 ms 1528 KB Output is correct
15 Correct 15 ms 1600 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1600 KB Output is correct
2 Correct 2 ms 1600 KB Output is correct
3 Correct 2 ms 1600 KB Output is correct
4 Correct 2 ms 1600 KB Output is correct
5 Correct 2 ms 1600 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1600 KB Output is correct
2 Correct 2 ms 1600 KB Output is correct
3 Correct 2 ms 1600 KB Output is correct
4 Correct 2 ms 1600 KB Output is correct
5 Correct 3 ms 1600 KB Output is correct
6 Correct 3 ms 1600 KB Output is correct
7 Correct 3 ms 1600 KB Output is correct
8 Correct 3 ms 1600 KB Output is correct
9 Correct 4 ms 1600 KB Output is correct
10 Correct 3 ms 1600 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1600 KB Output is correct
2 Correct 2 ms 1600 KB Output is correct
3 Correct 2 ms 1600 KB Output is correct
4 Correct 3 ms 1600 KB Output is correct
5 Correct 3 ms 1600 KB Output is correct
6 Correct 3 ms 1600 KB Output is correct
7 Correct 4 ms 1600 KB Output is correct
8 Correct 3 ms 1600 KB Output is correct
9 Correct 3 ms 1600 KB Output is correct
10 Correct 3 ms 1600 KB Output is correct
11 Correct 14 ms 1600 KB Output is correct
12 Correct 15 ms 1600 KB Output is correct
13 Correct 44 ms 3452 KB Output is correct
14 Correct 15 ms 3452 KB Output is correct
15 Correct 68 ms 3708 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3708 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3708 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3708 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3708 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -