제출 #67266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67266		theknife2001	곤돌라 (IOI14_gondola)	C++17	75 / 100	23 ms	2988 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;
const int N=250055;
int a[N];
int b[N];

int valid(int n, int inputSeq[])
{

    int j=0,x=1e9;
    for(int i=0;i<n;i++)
    {
        a[inputSeq[i]]++;
        if(x>inputSeq[i])
        {
            x=inputSeq[i];
            j=i;
        }
        if(a[inputSeq[i]]>1)
            return 0;
    }
    x++;
    for(int i=j+1;i<n;i++)
    {
        if(inputSeq[i]<=n)
        {
            if(inputSeq[i]==x)
            {
                x++;
                continue ;
            }
            return 0;
        }
        if(x>n)
            x=1;
        if(a[x]==0)
            x++;
        else
            return 0;
    }
    if(x>n)
        x=1;
    for(int i=0;i<j;i++)
    {
        if(inputSeq[i]<=n)
        {
            if(inputSeq[i]==x)
            {
                x++;
                continue ;
            }
            return 0;
        }
        if(a[x]==0)
            x++;
        else
            return 0;
    }
    return 1;

}



int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    bool q=0;
    for(int i=0;i<n;i++)
    {
        a[gondolaSeq[i]]=i+1;
        if(!q&&gondolaSeq[i]<=n)
        {
            q=1;
            int x=gondolaSeq[i];
            for(int j=i;j<n;j++)
            {
                b[j]=x;
                x++;
                if(x>n)
                    x=1;
            }
            for(int j=0;j<i;j++)
            {
                b[j]=x++;
                if(x>n)
                    x=1;
            }
        }
    }
    if(!q)
        for(int i=0;i<n;i++)
            b[i]=i+1;
    int x=n+1;
    int j=0;
    for(int i=n+1;i<N;i++)
    {
        if(!a[i])
            continue ;
        a[i]--;
        while(b[a[i]]!=i)
        {
            replacementSeq[j++]=b[a[i]];
            b[a[i]]=x;
            x++;
        }
    }
    return j;
}

int m=1e9+9;


long long pow(long long x, int i)
{
    if(i%2)
        return (pow(x,i-1)*x)%m;
    if(i==0)
        return 1;
    long long y=pow(x,i/2)%m;
    return (y*y)%m;
}


int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq))
        return 0;
    bool q=0;
    memset(a,0,sizeof a);
    for(int i=0;i<n;i++)
        a[inputSeq[i]]=i+1;
    if(!q)
        for(int i=0;i<n;i++)
            b[i]=i+1;
    int x=n+1;
    long long ans=1;
    long long cnt=0;
    for(int i=n+1;i<N;i++)
        if(a[i])
            cnt++;
    int last=n;
    for(int i=n+1;i<N;i++)
    {
        if(!a[i]||cnt==0)
            continue ;
        a[i]--;
        ans*=pow(cnt,(inputSeq[a[i]]-last)-1);
        ans%=m;
        last=inputSeq[a[i]];
        cnt--;
    }
    return ans;
}
    

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:137:9: warning: unused variable 'x' [-Wunused-variable]
     int x=n+1;
         ^

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