Submission #77760

#	Time	Username	Problem	Language	Result	Execution time	Memory
77760		Charis02	Gondola (IOI14_gondola)	C++14	100 / 100	51 ms	13128 KiB

gondola

#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 (stderr)

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 / 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