oj.uz

Submission #66472

# Submission time Handle Problem Language Result Execution time Memory
66472 2018-08-10T16:58:35 Z Kubalionzzale Gondola (IOI14_gondola) C++14
75 / 100
 62 ms 5160 KB 
#include "gondola.h"

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

long long int mod = 1e9 + 9;

long long int powmod(long long int a, long long int b)
{
    long long int res = 1;
    a %= mod;

    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }

    return res;
}

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 a[])
{
    bool visited[250010] = { 0 };
    int remember = -1;
    int max = 0;
    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;
                }
            }
        }
    }

    std::set<int> set;
    long long int multi = 0;
    for (int i = 0; i < n; ++i)
    {
        ++a[i];
        if (a[i] > max)
            max = a[i];

        if (a[i] > n)
            set.insert(a[i]), ++multi;
    }

    set.insert(n);

    if (max == n)
        return 1;

    long long int ans = 1LL;
    for (auto it = set.begin(); it != set.end(); ++it)
    {
        auto it2 = it;
        ++it2;
        if (it2 == set.end())
            break;

        long long int val1 = *it;
        long long int val2 = *it2;

        if (val2 - val1 == 1)
        {
            --multi;
        }
        else
        {
            ans = (ans * powmod(multi, val2 - val1 - 1)) % mod;
            --multi;
        }
    }

    return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:71: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 3 ms 504 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 2 ms 800 KB Output is correct
5 Correct 2 ms 800 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 800 KB Output is correct
2 Correct 3 ms 824 KB Output is correct
3 Correct 3 ms 824 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 3 ms 908 KB Output is correct
6 Correct 10 ms 1316 KB Output is correct
7 Correct 17 ms 1900 KB Output is correct
8 Correct 16 ms 2268 KB Output is correct
9 Correct 7 ms 2268 KB Output is correct
10 Correct 17 ms 2432 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2452 KB Output is correct
2 Correct 3 ms 2452 KB Output is correct
3 Correct 2 ms 2452 KB Output is correct
4 Correct 3 ms 2452 KB Output is correct
5 Correct 3 ms 2452 KB Output is correct
6 Correct 3 ms 2452 KB Output is correct
7 Correct 3 ms 2452 KB Output is correct
8 Correct 3 ms 2452 KB Output is correct
9 Correct 4 ms 2452 KB Output is correct
10 Correct 3 ms 2452 KB Output is correct
11 Correct 13 ms 2508 KB Output is correct
12 Correct 21 ms 2508 KB Output is correct
13 Correct 48 ms 4428 KB Output is correct
14 Correct 13 ms 4428 KB Output is correct
15 Correct 62 ms 4684 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4684 KB Output is correct
2 Correct 3 ms 4684 KB Output is correct
3 Correct 3 ms 4684 KB Output is correct
4 Correct 3 ms 4684 KB Output is correct
5 Correct 3 ms 4684 KB Output is correct
6 Correct 3 ms 4684 KB Output is correct
7 Correct 3 ms 4684 KB Output is correct
8 Correct 3 ms 4684 KB Output is correct
9 Correct 55 ms 5160 KB Output is correct
10 Correct 40 ms 5160 KB Output is correct
11 Correct 17 ms 5160 KB Output is correct
12 Correct 26 ms 5160 KB Output is correct
13 Incorrect 6 ms 5160 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5160 KB Output is correct
2 Correct 3 ms 5160 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 ms 5160 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 3 ms 5160 KB Output is correct
7 Correct 3 ms 5160 KB Output is correct
8 Correct 3 ms 5160 KB Output is correct
9 Correct 50 ms 5160 KB Output is correct
10 Correct 45 ms 5160 KB Output is correct
11 Correct 16 ms 5160 KB Output is correct
12 Correct 19 ms 5160 KB Output is correct
13 Incorrect 9 ms 5160 KB Output isn't correct
14 Halted 0 ms 0 KB -