Submission #731259

#	Time	Username	Problem	Language	Result	Execution time	Memory
731259		lucri	Gondola (IOI14_gondola)	C++17	55 / 100	17 ms	2764 KiB

gondola

#include <stdio.h>
#include <assert.h>
#include "gondola.h"


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;
}

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

int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)
        return 0;
    return -3;
}

• 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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10