Submission #93787

#	Time	Username	Problem	Language	Result	Execution time	Memory
93787		Bodo171	Gondola (IOI14_gondola)	C++14	90 / 100	28 ms	4856 KiB

gondola

#include "gondola.h"
#include <iostream>
using namespace std;
const int nmax=100005;
const long long mod=1000*1000*1000+9;
int ap[10*nmax];
int v[nmax];
int i,act;
void permuta(int a[],int b[],int n)
{
    int offset=0;
    for(int i=0;i<n;i++)
        if(a[i]<=n)
            offset=i+1-a[i];
    for(int i=0;i<n;i++)
        b[i]=a[(i+offset+n)%n];
}
int valid(int n, int inputSeq[])
{
  permuta(inputSeq,v,n);
  for(int i=0;i<n;i++)
    {
        if(v[i]<=n&&v[i]!=i+1)
           return 0;
        if(ap[v[i]]) return 0;
        ap[v[i]]=1;
   }

  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int l=0;
  permuta(gondolaSeq,v,n);
  int mx=0;
  for(i=0;i<n;i++)
  {
     ap[v[i]]=i+1;
     mx=max(mx,v[i]);
  }
  act=n;
  for(i=n+1;i<=mx;i++)
    if(ap[i])
  {
     replacementSeq[l++]=ap[i];
     act++;
     while(act<i)
     {
        replacementSeq[l++]=act;
        act++;
     }
  }
  return l;
}

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

int countReplacement(int n, int inputSeq[])
{
    long long f=0,ans=1;
  if(!valid(n,inputSeq)) return 0;
  bool ordered=1;
  for(int i=0;i<n;i++)
    if(ap[i])
      ordered=0;
  for(int i=1000*1000;i>n;i--)
  {
      if(ap[i])  ap[i]+=ap[i+1];
      else
      {
          ap[i]=ap[i+1];
          f=ap[i];
          if(f)ans=(1LL*ans*f)%mod;
      }
  }
  if(ordered)
  {
      f=n;
      ans=(1LL*ans*f)%mod;
  }
  return ans;
}

• 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