oj.uz

Submission #77760

# Submission time Handle Problem Language Result Execution time Memory
77760 2018-09-30T08:47:19 Z Charis02 Gondola (IOI14_gondola) C++14
100 / 100
 51 ms 13128 KB 
#include "gondola.h"
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXNUM 250002

using namespace std;

ll go[MAXNUM],freq2[MAXNUM];
map < ll,ll > freq;

int valid(int n, int inputSeq[])
{
    ll mini = 0;

    rep(i,0,n)
    {
        if(inputSeq[i] < inputSeq[mini])
        {
            mini = i;
        }

        freq[inputSeq[i]]++;
    }

    if(freq.size() != n)
        return false;

    ll cur = 1;
    ll num = (inputSeq[mini] > n) ? 1 : inputSeq[mini];

    rep(i,mini-num+1,mini+n-num+1)
    {
        ll x = (i+2*n)%n;

        if(inputSeq[x] > n)
            continue;

        if(inputSeq[x] != cur)
        {
            return false;
        }

        cur++;
    }

    return true;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    ll mini = 0;
    ll maxi = 0;

    rep(i,0,n)
    {
        if(gondolaSeq[i] < gondolaSeq[mini])
        {
            mini = i;
        }

        if(gondolaSeq[i] > gondolaSeq[maxi])
        {
            maxi = i;
        }
    }

    ll num = (gondolaSeq[mini] > n) ? 1 : gondolaSeq[mini];
    ll cur = 1;

    rep(x,mini-num+1,mini+n-num+1)
    {
        ll i = (x+2*n)%n;

        if(gondolaSeq[i] > n)
        {
            freq2[gondolaSeq[i]]++;
        }

//        cout << x << " " << gondolaSeq[i] << " " << cur<< endl;

        go[gondolaSeq[i]] = cur;

        cur++;
    }

    ll countt = 0;
    ll prev = go[gondolaSeq[maxi]];

    rep(i,n+1,gondolaSeq[maxi]+1)
    {
        if(i == gondolaSeq[maxi] || freq2[i] == 0)
        {
            replacementSeq[countt] = prev;
            prev = i;
        }
        else
        {
            replacementSeq[countt] = go[i];
        }

        countt++;
    }

    return countt;
}

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

ll mod = 1000000009;

ll fast_expo(ll vasi,ll ek)
{
    if(ek == 0)
        return 1;
    if(ek == 1)
        return vasi;

    unsigned ll x = fast_expo(vasi,ek/2);

    x = (x*x)%mod;

    if(ek%2==1)
    {
        x = (x*vasi)%mod;
    }

    return x;
}

int countReplacement(int n, int inputSeq[])
{
    ll countt = 0;
    ll maxi = 0;

    rep(i,0,n)
    {
        if(inputSeq[i] > n)
        {
            countt++;
        }

        if(inputSeq[i] > inputSeq[maxi])
        {
            maxi = i;
        }
    }
/*
    if(countt == 0)
    {
        ll cur = 1;

        rep(i,maxi+1,maxi+n+1)
        {
            ll x = i%n;

            if(inputSeq[x] != cur)
            {
                return 0;
            }

            cur++;
        }
    }
*/
    sort(inputSeq,inputSeq+n);
    unsigned ll res = 1;
    ll prev = n;

    if(countt == n)
        res = n;


    rep(i,0,n)
    {
        if(inputSeq[i] <= n)
            continue;

        res = (res*fast_expo(countt%mod,inputSeq[i] - prev - 1))%mod;
        prev = inputSeq[i];
        countt--;
    }

    return res;
}

/*
int main()
{
    ll q,n,ar[MAXNUM],res[MAXNUM];

    cin >> q >> n;

    rep(i,0,n)
    {
        cin >> ar[i];
    }

    if(q <= 3)
    {
        cout << valid(n,ar) << endl;
    }
    else if(q <= 6)
    {
        ll ans = replacement(n,ar,res);
        cout << ans << " ";

        rep(i,0,ans)
        {
            cout << res[i] << " ";
        }

        cout << endl;
    }
    else
    {
        cout << countReplacement(n,ar) << endl;
    }
}
*/

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(freq.size() != n)
        ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 708 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 764 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 2 ms 968 KB Output is correct
5 Correct 2 ms 968 KB Output is correct
6 Correct 18 ms 3540 KB Output is correct
7 Correct 42 ms 5808 KB Output is correct
8 Correct 35 ms 6584 KB Output is correct
9 Correct 11 ms 6584 KB Output is correct
10 Correct 41 ms 8060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8060 KB Output is correct
2 Correct 2 ms 8060 KB Output is correct
3 Correct 2 ms 8060 KB Output is correct
4 Correct 2 ms 8060 KB Output is correct
5 Correct 2 ms 8060 KB Output is correct
6 Correct 17 ms 8060 KB Output is correct
7 Correct 42 ms 8060 KB Output is correct
8 Correct 36 ms 8532 KB Output is correct
9 Correct 11 ms 8532 KB Output is correct
10 Correct 40 ms 9952 KB Output is correct
11 Correct 2 ms 9952 KB Output is correct
12 Correct 2 ms 9952 KB Output is correct
13 Correct 21 ms 9952 KB Output is correct
14 Correct 2 ms 9952 KB Output is correct
15 Correct 51 ms 10836 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 10836 KB Output is correct
3 Correct 3 ms 10836 KB Output is correct
4 Correct 2 ms 10836 KB Output is correct
5 Correct 2 ms 10836 KB Output is correct
6 Correct 2 ms 10836 KB Output is correct
7 Correct 2 ms 10836 KB Output is correct
8 Correct 2 ms 10836 KB Output is correct
9 Correct 2 ms 10836 KB Output is correct
10 Correct 2 ms 10836 KB Output is correct
11 Correct 19 ms 10836 KB Output is correct
12 Correct 25 ms 10836 KB Output is correct
13 Correct 16 ms 10836 KB Output is correct
14 Correct 12 ms 10836 KB Output is correct
15 Correct 23 ms 10836 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 10836 KB Output is correct
3 Correct 2 ms 10836 KB Output is correct
4 Correct 2 ms 10836 KB Output is correct
5 Correct 2 ms 10836 KB Output is correct
6 Correct 2 ms 10836 KB Output is correct
7 Correct 2 ms 10836 KB Output is correct
8 Correct 2 ms 10836 KB Output is correct
9 Correct 20 ms 10836 KB Output is correct
10 Correct 16 ms 10836 KB Output is correct
11 Correct 8 ms 10836 KB Output is correct
12 Correct 9 ms 10836 KB Output is correct
13 Correct 4 ms 10836 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 10836 KB Output is correct
3 Correct 2 ms 10836 KB Output is correct
4 Correct 2 ms 10836 KB Output is correct
5 Correct 2 ms 10836 KB Output is correct
6 Correct 2 ms 10836 KB Output is correct
7 Correct 2 ms 10836 KB Output is correct
8 Correct 2 ms 10836 KB Output is correct
9 Correct 22 ms 10836 KB Output is correct
10 Correct 17 ms 10836 KB Output is correct
11 Correct 8 ms 10836 KB Output is correct
12 Correct 9 ms 10836 KB Output is correct
13 Correct 3 ms 10836 KB Output is correct
14 Correct 27 ms 11232 KB Output is correct
15 Correct 49 ms 12300 KB Output is correct
16 Correct 8 ms 12300 KB Output is correct
17 Correct 20 ms 12888 KB Output is correct
18 Correct 12 ms 13128 KB Output is correct