oj.uz

Submission #775280

# Submission time Handle Problem Language Result Execution time Memory
775280 2023-07-06T09:22:33 Z boris_mihov Gondola (IOI14_gondola) C++17
75 / 100
 30 ms 5124 KB 
#include "gondola.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <set>

typedef long long llong;
const int MAXNUM = 250000 + 10;
const int MAXN = 100000 + 10;
const int MOD  = 1e9 + 9;
const int INF  = 1e9;

std::set <int> s;

llong power(llong num, llong base)
{
    if (base == 0)
    {
        return 1;
    }

    if (base & 1)
    {
        return (num * power(num, base - 1)) % MOD;
    }

    llong res = power(num, base / 2);
    return (res * res) % MOD;
}

int n;
int getPosDiff(int last, int curr)
{
    if (last > curr)
    {
        return n - last + curr;
    }

    return curr - last;
}

int valid(int N, int inputSeq[])
{
    n = N;
    int minPos = 0;
    for (int i = 1 ; i < n ; ++i)
    {
        if (s.count(inputSeq[i]))
        {
            return 0;
        }

        s.insert(inputSeq[i]);
        if (inputSeq[i] < inputSeq[minPos])
        {
            minPos = i;
        }
    }

    if (inputSeq[minPos] > n)
    {
        return 1;
    }

    for (int i = minPos - 1 ; i >= std::max(0, minPos - inputSeq[minPos] + 1) ; --i)
    {
        if (inputSeq[i] <= n)
        {
            return 0;
        }
    }

    if (minPos + 1 < inputSeq[minPos])
    {
        for (int i = n - 1 ; i >= n + minPos + 1 - inputSeq[minPos] ; --i)
        {
            if (inputSeq[i] <= n)
            {
                return 0;
            }
        }
    }

    int lastPos = minPos;
    int last = inputSeq[minPos];
    for (int i = minPos + 1 ; i < n ; ++i)
    {
        if (inputSeq[i] <= n)
        {
            if (last > inputSeq[i])
            {
                return 0;
            }
            
            if (getPosDiff(lastPos, i) != inputSeq[i] - last)
            {
                return 0;
            }

            last = inputSeq[i];
            lastPos = i;
        }
    }

    for (int i = 1 ; i < minPos ; ++i)
    {
        if (inputSeq[i] <= n)
        {
            if (last > inputSeq[i])
            {
                return 0;
            }
            
            if (getPosDiff(lastPos, i) != inputSeq[i] - last)
            {
                return 0;
            }

            last = inputSeq[i];
            lastPos = i;
        }
    }

    return 1;
}

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

int a[MAXN];
int res[MAXNUM];
int sorted[MAXN];
int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
    n = N;
    int minPos = 0;
    for (int i = 1 ; i < n ; ++i)
    {
        if (gondolaSeq[i] < gondolaSeq[minPos])
        {
            minPos = i;
        }
    }

    int cnt = gondolaSeq[minPos];
    if (cnt > n) cnt = 1;

    for (int i = minPos ; i < n ; ++i)
    {
        a[i] = cnt++;
        if (cnt == n + 1)
        {
            cnt = 1;
        }
    }

    for (int i = 0 ; i < minPos ; ++i)
    {
        a[i] = cnt++;
        if (cnt == n + 1)
        {
            cnt = 1;
        }
    }

    std::iota(sorted, sorted + n, 0);
    std::sort(sorted, sorted + n, [&](int x, int y)
    {
        return gondolaSeq[x] < gondolaSeq[y];
    });

    int len = 0, reached = n;
    for (int i = 0 ; i < n ; ++i)
    {
        if (gondolaSeq[sorted[i]] <= reached)
        {
            assert(gondolaSeq[sorted[i]] <= n);
            continue;
        }

        replacementSeq[len++] = a[sorted[i]];
        reached++;

        while (gondolaSeq[sorted[i]] > reached)
        {
            replacementSeq[len++] = reached;
            reached++;
        }
    }

    return len;
}

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

int countReplacement(int N, int inputSeq[])
{
    if (!valid(N, inputSeq))
    {
        return 0;
    }

    std::vector <int> vals;
    for (int i = 0 ; i < n ; ++i)
    {
        if (inputSeq[i] > n)
        {
            vals.push_back(inputSeq[i]);
        }
    }

    int last = n;
    llong ans = 1;
    std::sort(vals.begin(), vals.end());
    for (int i = 0 ; i < vals.size() ; ++i)
    {
        ans *= power(vals.size() - i, vals[i] - last - 1);
        last = vals[i];
        ans %= MOD;
    }

    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:216:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for (int i = 0 ; i < vals.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 10 ms 2380 KB Output is correct
7 Correct 7 ms 1144 KB Output is correct
8 Correct 19 ms 4244 KB Output is correct
9 Correct 6 ms 1564 KB Output is correct
10 Correct 23 ms 4940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 13 ms 2432 KB Output is correct
7 Correct 7 ms 1080 KB Output is correct
8 Correct 19 ms 4308 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 23 ms 4900 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 312 KB Output is correct
13 Correct 11 ms 2260 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 28 ms 5124 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 8 ms 1616 KB Output is correct
12 Correct 9 ms 1876 KB Output is correct
13 Correct 11 ms 1584 KB Output is correct
14 Correct 9 ms 1684 KB Output is correct
15 Correct 16 ms 2376 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
0 / 15.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 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 30 ms 4876 KB Output is correct
10 Correct 27 ms 4148 KB Output is correct
11 Correct 9 ms 1740 KB Output is correct
12 Correct 12 ms 2008 KB Output is correct
13 Incorrect 4 ms 724 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 29 ms 4812 KB Output is correct
10 Correct 23 ms 4168 KB Output is correct
11 Correct 10 ms 1748 KB Output is correct
12 Correct 12 ms 2092 KB Output is correct
13 Incorrect 3 ms 712 KB Output isn't correct
14 Halted 0 ms 0 KB -