Submission #1152097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152097		alexdd	Gondola (IOI14_gondola)	C++20	90 / 100	54 ms	4680 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
    map<int,int> idk;
    for(int i=0;i<n;i++)
    {
        if(idk[inputSeq[i]])
            return 0;
        idk[inputSeq[i]]++;
    }
    for(int i=0;i<n;i++)
    {
        if(inputSeq[i] <= n)
        {
            for(int j=0;j<n;j++)
            {
                if(inputSeq[(i+j)%n]<=n && inputSeq[(i+j)%n] != (inputSeq[i]-1 + j)%n + 1)
                    return 0;
            }
            return 1;
        }
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    for(int i=0;i<n;i++)
        gondolaSeq[i]--;
    vector<int> init(n),init_poz(250000,-1),final_poz(250000,-1);
    int maxv=-1;
    for(int i=0;i<n;i++)
    {
        final_poz[gondolaSeq[i]]=i;
        maxv = max(maxv, gondolaSeq[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(gondolaSeq[i]<n || i==n-1)
        {
            for(int j=0;j<n;j++)
                init[(i+j)%n] = (gondolaSeq[i]+j)%n;
            for(int j=0;j<n;j++)
                init_poz[init[j]]=j;
            int lun=0;
            for(int j=n;j<=maxv;j++)
            {
                if(final_poz[j]==-1)
                {
                    bool gasit=0;
                    for(int u=0;u<n;u++)
                    {
                        if(final_poz[init[u]] == -1)
                        {
                            replacementSeq[lun++] = init[u];
                            init[u] = j;
                            init_poz[j] = u;
                            init_poz[replacementSeq[lun-1]] = -1;
                            gasit=1;
                            break;
                        }
                    }
                    assert(gasit);
                }
                else
                {
                    replacementSeq[lun++] = init[final_poz[j]];
                    init[final_poz[j]] = j;
                    init_poz[j] = final_poz[j];
                    init_poz[replacementSeq[lun-1]] = -1;
                }
            }
            for(int i=0;i<lun;i++)
                replacementSeq[i]++;
            return lun;
        }
    }
    assert(0);
}

//----------------------
#define ll long long
const ll MOD = 1e9+9;
int countReplacement(int n, int gondolaSeq[])
{
    if(!valid(n,gondolaSeq))
        return 0;
    for(int i=0;i<n;i++)
        gondolaSeq[i]--;
    vector<int> init(n),final_poz(250000,-1);
    int maxv=-1;
    for(int i=0;i<n;i++)
    {
        final_poz[gondolaSeq[i]]=i;
        maxv = max(maxv, gondolaSeq[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(gondolaSeq[i]<n || i==n-1)
        {
            for(int j=0;j<n;j++)
                init[(i+j)%n] = (gondolaSeq[i]+j)%n;
            set<int> proaste;
            for(int j=0;j<n;j++)
                if(final_poz[init[j]]==-1)
                    proaste.insert(j);
            ll rez=1;
            for(int j=n;j<=maxv;j++)
            {
                if(final_poz[j]==-1)
                {
                    assert(!proaste.empty());
                    int u = *proaste.begin();
                    assert(final_poz[init[u]] == -1);
                    init[u] = j;
                    rez = (rez*(ll)proaste.size())%MOD;
                }
                else
                {
                    init[final_poz[j]] = j;
                    proaste.erase(final_poz[j]);
                }
            }
            if(gondolaSeq[i]>=n)
            {
                rez = rez*n%MOD;
            }
            return rez;
        }
    }
    assert(0);
}

• 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