Submission #281677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
281677	2020-08-23T09:52:55 Z	SamAnd	Gondola (IOI14_gondola)	C++17	100 / 100	65 ms	6392 KB

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

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.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	15 ms	2432 KB	Output is correct
7	Correct	33 ms	3968 KB	Output is correct
8	Correct	25 ms	4240 KB	Output is correct
9	Correct	7 ms	1536 KB	Output is correct
10	Correct	28 ms	4864 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	14 ms	2432 KB	Output is correct
7	Correct	34 ms	3960 KB	Output is correct
8	Correct	24 ms	4224 KB	Output is correct
9	Correct	9 ms	1536 KB	Output is correct
10	Correct	28 ms	4864 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	23 ms	2304 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	51 ms	4984 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	256 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct
4	Correct	384 KB	Output is correct
5	Correct	384 KB	Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	10 ms	896 KB	Output is correct
12	Correct	12 ms	1024 KB	Output is correct
13	Correct	17 ms	1424 KB	Output is correct
14	Correct	10 ms	896 KB	Output is correct
15	Correct	24 ms	2296 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	384 KB	Output is correct
2	Correct	256 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	43 ms	4284 KB	Output is correct
10	Correct	36 ms	3712 KB	Output is correct
11	Correct	12 ms	1536 KB	Output is correct
12	Correct	16 ms	1792 KB	Output is correct
13	Correct	4 ms	640 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	42 ms	4344 KB	Output is correct
10	Correct	33 ms	3712 KB	Output is correct
11	Correct	12 ms	1536 KB	Output is correct
12	Correct	15 ms	1792 KB	Output is correct
13	Correct	4 ms	640 KB	Output is correct
14	Correct	58 ms	4856 KB	Output is correct
15	Correct	65 ms	6392 KB	Output is correct
16	Correct	10 ms	1408 KB	Output is correct
17	Correct	39 ms	4472 KB	Output is correct
18	Correct	22 ms	2688 KB	Output is correct