Submission #731269

#	Time	Username	Problem	Language	Result	Execution time	Memory
731269		lucri	Gondola (IOI14_gondola)	C++17	90 / 100	18 ms	2600 KiB

gondola

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


int poz[100010];
bool e[250010];
int valid(int n, int inputSeq[])
{
    for(int i=0;i<=n;++i)
    {
        if(e[inputSeq[i]])
            return 0;
        e[inputSeq[i]]=true;
        if(1<=inputSeq[i]&&inputSeq[i]<=n)
            poz[inputSeq[i]]=i+1;
    }
    int dif=-1;
    for(int i=1;i<=n;++i)
        if(poz[i])
        {
            int val;
            if(i<=poz[i])
                val=poz[i]-i;
            else
                val=poz[i]+n-i;
            if(dif==-1)
                dif=val;
            else if(dif!=val)
                return 0;
        }
    return 1;
}

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

int ago[100010];

int truevalue(int val,int n)
{
    while(val<=0)
        val+=n;
    return val;
}

int goodshift(int n,int gondolaSeq[])
{
    int ls=-1;
    for(int i=0;i<n;++i)
        if(1<=gondolaSeq[i]&&gondolaSeq[i]<=n)
        {
            if(gondolaSeq[i]<=i+1)
                ls=i+1-gondolaSeq[i];
            else
                ls=i+1+n-gondolaSeq[i];
            break;
        }
    if(ls==-1)
    {
        for(int i=0;i<n;++i)
            ago[i+1]=gondolaSeq[i];
        return 0;
    }
    for(int i=0;i<n;++i)
        ago[truevalue(i+1-ls,n)]=gondolaSeq[i];
    return 1;
}

int pozval[250010],valac;

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    goodshift(n,gondolaSeq);
    for(int i=1;i<=n;++i)
        pozval[ago[i]]=i;
    valac=n;
    for(int i=1;i<=n;++i)
        ago[i]=i;
    for(int i=n+1;i<=250000;++i)
    {
        if(pozval[i]!=0)
        {
            while(valac<i)
            {
                replacementSeq[valac-n]=ago[pozval[i]];
                ++valac;
                ago[pozval[i]]=valac;
            }
        }
    }
    return valac-n;
}

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

long long ans=1;

long long putere(long long a,long long b)
{
    if(b==0)
        return 1;
    long long m=putere(a,b/2);
    m*=m;
    m%=MOD;
    if(b%2)
    {
        m*=a;
        m%=MOD;
    }
    return m;
}

int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)
        return 0;
    std::sort(inputSeq,inputSeq+n);
    if(inputSeq[0]>n)
        ans*=n;
    int poz=0;
    while(poz<n&&inputSeq[poz]<=n)
        ++poz;
    if(poz!=0)
        inputSeq[poz-1]=n;
    for(;poz<n;++poz)
    {
        if(poz==0)
            ans*=putere(n-poz,inputSeq[poz]-n-1);
        else
            ans*=putere(n-poz,inputSeq[poz]-inputSeq[poz-1]-1);
        ans%=MOD;
    }
    return ans;
}

• 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: 0 / 10