oj.uz

Submission #66474

# Submission time Handle Problem Language Result Execution time Memory
66474 2018-08-10T17:03:40 Z Kubalionzzale Gondola (IOI14_gondola) C++14
100 / 100
 183 ms 10768 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 };
    std::set<int> happen;
    int remember = -1;
    int max = 0;
    for (int i = 0; i < n; ++i)
    {
        --a[i];
        if (happen.find(a[i]) != happen.end())
            return 0;
        else
            happen.insert(a[i]);

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

    if (remember == -1)
        ans *= n;
    ans %= mod;

    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 };
         ^~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:141:10: warning: unused variable 'visited' [-Wunused-variable]
     bool visited[250010] = { 0 };
          ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 748 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 8 ms 952 KB Output is correct
7 Correct 16 ms 1080 KB Output is correct
8 Correct 15 ms 1080 KB Output is correct
9 Correct 9 ms 1080 KB Output is correct
10 Correct 17 ms 1124 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1124 KB Output is correct
2 Correct 2 ms 1124 KB Output is correct
3 Correct 3 ms 1124 KB Output is correct
4 Correct 3 ms 1124 KB Output is correct
5 Correct 3 ms 1124 KB Output is correct
6 Correct 8 ms 1124 KB Output is correct
7 Correct 18 ms 1148 KB Output is correct
8 Correct 24 ms 1148 KB Output is correct
9 Correct 7 ms 1148 KB Output is correct
10 Correct 15 ms 1148 KB Output is correct
11 Correct 2 ms 1148 KB Output is correct
12 Correct 2 ms 1148 KB Output is correct
13 Correct 8 ms 1148 KB Output is correct
14 Correct 2 ms 1148 KB Output is correct
15 Correct 22 ms 1148 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1148 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 2 ms 1148 KB Output is correct
4 Correct 2 ms 1148 KB Output is correct
5 Correct 2 ms 1148 KB Output is correct
6 Correct 2 ms 1148 KB Output is correct
7 Correct 3 ms 1148 KB Output is correct
8 Correct 3 ms 1148 KB Output is correct
9 Correct 3 ms 1148 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Correct 15 ms 1196 KB Output is correct
12 Correct 16 ms 1196 KB Output is correct
13 Correct 45 ms 3116 KB Output is correct
14 Correct 13 ms 3116 KB Output is correct
15 Correct 84 ms 3372 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3372 KB Output is correct
2 Correct 2 ms 3372 KB Output is correct
3 Correct 3 ms 3372 KB Output is correct
4 Correct 2 ms 3372 KB Output is correct
5 Correct 2 ms 3372 KB Output is correct
6 Correct 2 ms 3372 KB Output is correct
7 Correct 2 ms 3372 KB Output is correct
8 Correct 2 ms 3372 KB Output is correct
9 Correct 110 ms 7100 KB Output is correct
10 Correct 78 ms 7100 KB Output is correct
11 Correct 32 ms 7100 KB Output is correct
12 Correct 34 ms 7100 KB Output is correct
13 Correct 8 ms 7100 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7100 KB Output is correct
2 Correct 2 ms 7100 KB Output is correct
3 Correct 2 ms 7100 KB Output is correct
4 Correct 26 ms 7100 KB Output is correct
5 Correct 2 ms 7100 KB Output is correct
6 Correct 3 ms 7100 KB Output is correct
7 Correct 2 ms 7100 KB Output is correct
8 Correct 3 ms 7100 KB Output is correct
9 Correct 112 ms 7164 KB Output is correct
10 Correct 83 ms 7164 KB Output is correct
11 Correct 30 ms 7164 KB Output is correct
12 Correct 35 ms 7164 KB Output is correct
13 Correct 8 ms 7164 KB Output is correct
14 Correct 165 ms 8920 KB Output is correct
15 Correct 183 ms 10768 KB Output is correct
16 Correct 28 ms 10768 KB Output is correct
17 Correct 102 ms 10768 KB Output is correct
18 Correct 52 ms 10768 KB Output is correct