제출 #1152103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152103		alexdd	곤돌라 (IOI14_gondola)	C++20	60 / 100	33 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]--;
    int maxv=-1;
    map<int,bool> ap;
    for(int i=0;i<n;i++)
    {
        if(gondolaSeq[i]<n)
            continue;
        ap[gondolaSeq[i]]=1;
        maxv = max(maxv, gondolaSeq[i]);
    }
    bool all_big=1;
    for(int i=0;i<n;i++)
        if(gondolaSeq[i]<n)
            all_big=0;

    ll cnt=n,rez=1;
    for(int j=n;j<=maxv;j++)
    {
        if(!ap[j])
        {
            assert(cnt>0);
            rez = rez*cnt%MOD;
        }
        else
        {
            cnt--;
        }
    }
    if(all_big)
        rez = rez*n%MOD;
    return rez;
}

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