Submission #7306

#	Time	Username	Problem	Language	Result	Execution time	Memory
7306		gs13068	Gondola (IOI14_gondola)	C++98	100 / 100	24 ms	4412 KiB

gondola

#include "gondola.h"
#include <algorithm>

#define MOD 1000000009

int arr[250001];
int now[250001];

int valid(int n, int inputSeq[])
{
  int i,j;
  for(i=0;i<n;i++)if(inputSeq[i]<=n)break;
  if(i<n)for(j=0;j<n;j++)if(inputSeq[j]<=n&&(inputSeq[j]+i)%n!=(inputSeq[i]+j)%n)return 0;
  std::sort(inputSeq,inputSeq+n);
  for(i=1;i<n;i++)if(inputSeq[i-1]==inputSeq[i])return 0;
  return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int i,j;
  for(i=0;i<n;i++)arr[gondolaSeq[i]]=i+1;
  for(i=0;i<n;i++)if(gondolaSeq[i]<=n)break;
  for(j=0;j<n;j++)now[j]=i<n?(gondolaSeq[i]+j-i+n-1)%n+1:j+1;
  j=0;
  for(i=0;i<n;i++)if(gondolaSeq[i]>j)j=gondolaSeq[i];
  for(i=n+1;i<=j;i++)
  {
    replacementSeq[i-n-1]=arr[i]>0?now[arr[i]-1]:now[arr[j]-1];
    now[arr[i]>0?arr[i]-1:arr[j]-1]=i;
  }
  return j-n;
}

int f(int x,int y)
{
  if(y==0||x==1)return 1;
  if(y&1)return 1LL*x*f(x,y-1)%MOD;
  x=f(x,y>>1);
  return 1LL*x*x%MOD;
}

int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))return 0;
  int i,r=1;
  std::sort(inputSeq,inputSeq+n);
  for(i=0;i<n;i++)
  {
    if(inputSeq[i]<=n)continue;
    r=1LL*r*f(n-i,inputSeq[i]-(i>0?std::max(inputSeq[i-1],n):n)-1)%MOD;
  }
  return 1LL*r*(inputSeq[0]>n?n:1)%MOD;
}

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