Submission #281677

#	Time	Username	Problem	Language	Result	Execution time	Memory
281677		SamAnd	Gondola (IOI14_gondola)	C++17	100 / 100	65 ms	6392 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005, M = 1000000009;

int n;
int a[N];

int valid(int n, int inputSeq[])
{
    ::n = n;
    for (int i = 0; i < n; ++i)
        a[i] = inputSeq[i];

    set<int> s;
    for (int i = 0; i < n; ++i)
        s.insert(a[i]);
    if (sz(s) != n)
        return 0;

    int minu = M;
    int mini;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < minu)
        {
            minu = a[i];
            mini = i;
        }
    }

    int q = 0;
    for (int i = mini; i < n; ++i)
    {
        if (a[i] <= n)
        {
            if (a[i] != minu + q)
                return 0;
        }
        ++q;
    }
    for (int i = 0; i < mini; ++i)
    {
        if (a[i] <= n)
        {
            if (a[i] != minu + q)
                return 0;
        }
        ++q;
    }

    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    ::n = n;
    for (int i = 0; i < n; ++i)
        a[i] = gondolaSeq[i];

    int m = 0;

    vector<pair<int, int> > v;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > n)
        {
            v.push_back(m_p(a[i], i));
        }
    }

    sort(all(v));
    reverse(all(v));

    ///////////////////////////////////////////
    int minu = M;
    int mini;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] < minu)
        {
            minu = a[i];
            mini = i;
        }
    }

    if (minu > n)
    {
        minu = 1;
    }

    for (int i = mini; i < n; ++i)
    {
        if (minu > n)
            minu = 1;
        a[i] = minu;
        ++minu;
    }
    for (int i = 0; i < mini; ++i)
    {
        if (minu > n)
            minu = 1;
        a[i] = minu;
        ++minu;
    }
    ///////////////////////////////////////////

    int u = n + 1;
    while (!v.empty())
    {
        if (u == v.back().fi)
        {
            replacementSeq[m++] = a[v.back().se];
            a[v.back().se] = u;
            v.pop_back();
        }
        else
        {
            replacementSeq[m++] = a[v.back().se];
            a[v.back().se] = u;
        }
        ++u;
    }

    return m;
}

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

int ast(int x, int n)
{
    int ans = 1;
    while (n)
    {
        if (n % 2 == 1)
            ans = (ans * 1LL * x) % M;
        x = (x * 1LL * x) % M;
        n /= 2;
    }
    return ans;
}

int countReplacement(int n, int inputSeq[])
{
    if (valid(n, inputSeq) == 0)
        return 0;

    ::n = n;
    for (int i = 0; i < n; ++i)
        a[i] = inputSeq[i];

    vector<pair<int, int> > v;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > n)
        {
            v.push_back(m_p(a[i], i));
        }
    }

    sort(all(v));
    reverse(all(v));

    bool z = (sz(v) == n);

    int ans = 1;

    int u = n + 1;
    while (!v.empty())
    {
        if (u == v.back().fi)
        {
            v.pop_back();
            ++u;
        }
        else
        {
            ans = (ans * 1LL * ast(sz(v), v.back().fi - u)) % M;
            u = v.back().fi;
        }
    }

    if (z)
        ans = (ans * 1LL * n) % M;

    return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:28:9: warning: 'mini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |     int mini;
      |         ^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:9: warning: 'mini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     int mini;
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10