oj.uz

Submission #46767

# Submission time Handle Problem Language Result Execution time Memory
46767 2018-04-23T04:20:57 Z RayaBurong25_1 Gondola (IOI14_gondola) C++17
75 / 100
 33 ms 4408 KB 
#include "gondola.h"
#include <vector>
#include <algorithm>
#define MOD 1000000009LL
int Vis[250005];
int valid(int n, int inputSeq[])
{
    int i, r = -1;
    for (i = 0; i < n; i++)
    {
        if (Vis[inputSeq[i]])
            return 0;
        Vis[inputSeq[i]] = 1;
        if (inputSeq[i] <= n)
        {
            if (r == -1)
                r = (inputSeq[i] + n - (i + 1))%n;
            else if ((inputSeq[i] + n - (i + 1))%n != r)
                return 0;
        }
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int i, r = -1;
    for (i = 0; i < n; i++)
    {
        if (gondolaSeq[i] <= n)
        {
            if (r == -1)
            {
                r = (gondolaSeq[i] + n - (i + 1))%n;
                break;
            }
        }
    }
    if (r == -1)
        r = 0;
    std::vector<std::pair<int, int> > V;
    for (i = 0; i < n; i++)
    {
        if (gondolaSeq[i] > n)
        {
            V.push_back({gondolaSeq[i], i});
            gondolaSeq[i] = (i + r)%n + 1;
        }
    }
    if (V.size() == 0)
        return 0;
    std::sort(V.begin(), V.end());
    r = 0;
    int j = 0;
    for (i = n + 1; i <= V.back().first; i++)
    {
        replacementSeq[r] = gondolaSeq[V[j].second];
        gondolaSeq[V[j].second] = i;
        if (V[j].first == i)
            j++;
        r++;
    }
    return r;
}

//----------------------
long long pow(long long b, int e)
{
    if (e == 0)
        return 1LL;
    else if (e == 1)
        return b;
    else
    {
        long long r = pow(b, e/2);
        r = (r*r)%MOD;
        if (e%2)
            r = (r*b)%MOD;
        return r;
    }
}
int countReplacement(int n, int inputSeq[])
{
    int i, r = -1;
    for (i = 0; i < n; i++)
    {
        if (Vis[inputSeq[i]])
            return 0;
        Vis[inputSeq[i]] = 1;
        if (inputSeq[i] <= n)
        {
            if (r == -1)
                r = (inputSeq[i] + n - (i + 1))%n;
            else if ((inputSeq[i] + n - (i + 1))%n != r)
                return 0;
        }
    }
    std::vector<std::pair<int, int> > V;
    for (i = 0; i < n; i++)
    {
        if (inputSeq[i] > n)
        {
            V.push_back({inputSeq[i], i});
            inputSeq[i] = (i + r)%n + 1;
        }
    }
    if (V.size() == 0)
        return 1;
    std::sort(V.begin(), V.end());
    long long ans = 1;
    int j;
    for (j = 0; j < V.size(); j++)
    {
        if (j == 0)
            ans = (ans*pow(V.size() - j, V[j].first - n - 1))%MOD;
        else
            ans = (ans*pow(V.size() - j, V[j].first - V[j - 1].first - 1))%MOD;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < V.size(); j++)
                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 476 KB Output is correct
6 Correct 6 ms 792 KB Output is correct
7 Correct 21 ms 928 KB Output is correct
8 Correct 12 ms 1132 KB Output is correct
9 Correct 7 ms 1132 KB Output is correct
10 Correct 13 ms 1148 KB Output is correct

Subtask #3
10.0 / 10.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 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 7 ms 1148 KB Output is correct
7 Correct 19 ms 1148 KB Output is correct
8 Correct 11 ms 1148 KB Output is correct
9 Correct 4 ms 1148 KB Output is correct
10 Correct 12 ms 1148 KB Output is correct
11 Correct 9 ms 1148 KB Output is correct
12 Correct 2 ms 1148 KB Output is correct
13 Correct 7 ms 1148 KB Output is correct
14 Correct 2 ms 1148 KB Output is correct
15 Correct 20 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 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

Subtask #5
10.0 / 10.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 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 2 ms 1148 KB Output is correct
8 Correct 2 ms 1148 KB Output is correct
9 Correct 2 ms 1148 KB Output is correct
10 Correct 2 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 2 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 2 ms 1148 KB Output is correct
8 Correct 2 ms 1148 KB Output is correct
9 Correct 2 ms 1148 KB Output is correct
10 Correct 2 ms 1148 KB Output is correct
11 Correct 11 ms 1148 KB Output is correct
12 Correct 13 ms 1148 KB Output is correct
13 Correct 17 ms 1584 KB Output is correct
14 Correct 12 ms 1584 KB Output is correct
15 Correct 25 ms 2452 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2452 KB Output is correct
2 Correct 2 ms 2452 KB Output is correct
3 Correct 2 ms 2452 KB Output is correct
4 Correct 2 ms 2452 KB Output is correct
5 Correct 2 ms 2452 KB Output is correct
6 Correct 2 ms 2452 KB Output is correct
7 Correct 2 ms 2452 KB Output is correct
8 Correct 2 ms 2452 KB Output is correct
9 Correct 21 ms 3020 KB Output is correct
10 Correct 26 ms 3020 KB Output is correct
11 Correct 9 ms 3020 KB Output is correct
12 Correct 10 ms 3120 KB Output is correct
13 Incorrect 4 ms 3120 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3120 KB Output is correct
2 Correct 2 ms 3120 KB Output is correct
3 Correct 2 ms 3120 KB Output is correct
4 Correct 2 ms 3120 KB Output is correct
5 Correct 2 ms 3120 KB Output is correct
6 Correct 2 ms 3120 KB Output is correct
7 Correct 2 ms 3120 KB Output is correct
8 Correct 2 ms 3120 KB Output is correct
9 Correct 33 ms 4184 KB Output is correct
10 Correct 20 ms 4392 KB Output is correct
11 Correct 9 ms 4392 KB Output is correct
12 Correct 10 ms 4408 KB Output is correct
13 Incorrect 4 ms 4408 KB Output isn't correct
14 Halted 0 ms 0 KB -