Submission #93790

#	Time	Username	Problem	Language	Result	Execution time	Memory
93790		Bodo171	Gondola (IOI14_gondola)	C++14	100 / 100	101 ms	10892 KiB

gondola

#include "gondola.h"
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int nmax=100005;
const long long mod=1000*1000*1000+9;
map<int,int> ap;
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;
}

//----------------------
long long expo(long long A,int B)
{
    long long ret=1,p2=A;
    for(int p=0;p<=30;p++)
    {
        if(((1<<p)&B))
             ret=(1LL*ret*p2)%mod;
        p2=(1LL*p2*p2)%mod;
    }
    return ret;
}
int countReplacement(int n, int inputSeq[])
{
    long long f=0,ans=1;
  if(!valid(n,inputSeq)) return 0;
  bool ordered=1;
  for(int i=1;i<=n;i++)
    if(ap[i])
      ordered=0;
  sort(inputSeq,inputSeq+n);
  for(i=n-2;i>=0;i--)
    if(inputSeq[i]>n||inputSeq[i+1]>n)
  {
      f=n-1-i;if(inputSeq[i]<n) inputSeq[i]=n;
      ans=(1LL*ans*expo(f,inputSeq[i+1]-inputSeq[i]-1))%mod;
  }
  if(ordered)
  {
      f=n;
      ans=(1LL*ans*expo(f,inputSeq[0]-n-1))%mod;
      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: 10 / 10