Submission #7559

#	Time	Username	Problem	Language	Result	Execution time	Memory
7559		baneling100	Gondola (IOI14_gondola)	C++98	100 / 100	64 ms	5096 KiB

gondola

#include "gondola.h"
#include <algorithm>
#include <vector>
#define MOD 1000000009

using namespace std;

typedef pair <int,int> ppair;
vector <ppair> A;
int Check[250001], L;
long long Num, B[101];

int valid(int n, int inputSeq[])
{
    int i, X=-1, Y;

    for(i=0 ; i<n ; i++)
    {
        if(Check[inputSeq[i]])
            return 0;
        Check[inputSeq[i]]=1;
        if(inputSeq[i]<=n)
        {
            X=i;
            Y=inputSeq[i];
        }
    }
    if(X==-1)
        return 1;
    for(i=X+1 ; i<n ; i++)
    {
        Y++;
        if(Y>n)
            Y=1;
        if(inputSeq[i]<=n && inputSeq[i]!=Y)
            return 0;
    }
    for(i=0 ; i<=X-1 ; i++)
    {
        Y++;
        if(Y>n)
            Y=1;
        if(inputSeq[i]<=n && inputSeq[i]!=Y)
            return 0;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int i, X=-1, Y, Size;

    for(i=0 ; i<n ; i++)
        if(gondolaSeq[i]<=n)
        {
            X=i;
            Y=gondolaSeq[i];
            break;
        }
    if(X==-1)
        for(i=0 ; i<n ; i++)
            A.push_back(make_pair(gondolaSeq[i],i+1));
    else
    {
        for(i=X+1 ; i<n ; i++)
        {
            Y++;
            if(Y>n)
                Y=1;
            if(gondolaSeq[i]>n)
                A.push_back(make_pair(gondolaSeq[i],Y));
        }
        for(i=0 ; i<=X-1 ; i++)
        {
            Y++;
            if(Y>n)
                Y=1;
            if(gondolaSeq[i]>n)
                A.push_back(make_pair(gondolaSeq[i],Y));
        }
    }
    sort(A.begin(),A.end());
    X=0;
    Y=n+1;
    Size=A.size();
    while(X<Size)
    {
        replacementSeq[L++]=A[X].second;
        A[X].second=Y;
        Y++;
        if(A[X].first==A[X].second)
            X++;
    }
    return L;
}

long long Multi(int X, int Y)
{
    int i, Z;
    long long Temp;

    B[0]=Y;
    for(i=1 ; i<=50 ; i++)
    {
        B[i]=B[i-1]*B[i-1];
        B[i]%=MOD;
    }
    Temp=1;
    Z=0;
    while(X)
    {
        if(X&1)
            Temp*=B[Z];
        Z++;
        X>>=1;
        Temp%=MOD;
    }
    return Temp;
}

int countReplacement(int n, int inputSeq[])
{
    int i, j, X=-1, Y;

    for(i=0 ; i<n ; i++)
    {
        A.push_back(make_pair(inputSeq[i],0));
        if(inputSeq[i]<=n)
        {
            X=i;
            Y=inputSeq[i];
        }
    }
    sort(A.begin(),A.end());
    j=A.size();
    for(i=1 ; i<j ; i++)
        if(A[i].first==A[i-1].first)
            return 0;
    for(i=X+1 ; i<n ; i++)
    {
        Y++;
        if(Y>n)
            Y=1;
        if(inputSeq[i]<=n && inputSeq[i]!=Y)
            return 0;
    }
    for(i=0 ; i<=X-1 ; i++)
    {
        Y++;
        if(Y>n)
            Y=1;
        if(inputSeq[i]<=n && inputSeq[i]!=Y)
            return 0;
    }
    A.clear();
    A.push_back(make_pair(n,0));
    X=1;
    for(i=0 ; i<n ; i++)
    {
        if(inputSeq[i]>n)
            A.push_back(make_pair(inputSeq[i],0));
        else
            X=0;
    }
    if(X)
        Num=n;
    else
        Num=1;
    sort(A.begin(),A.end());
    j=A.size();
    for(i=1 ; i<j ; i++)
    {
        Num*=Multi(A[i].first-A[i-1].first-1,j-i);
        Num%=MOD;
    }
    return Num;
}

• 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