Submission #428428

#	Time	Username	Problem	Language	Result	Execution time	Memory
428428		TLP39	Gondola (IOI14_gondola)	C++14	75 / 100	48 ms	4512 KiB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int valid(int n, int seq[])
{
    map<int,int> mp;
    bool ch=true;
    int temp=-1;
    for(int i=0;i<n;i++)
    {
        if(seq[i]<=n)
        {
            if(ch)
            {
                ch=false;
                temp=(seq[i]-i+n)%n;
            }
            else if((seq[i]-i+n)%n!=temp) return 0;
        }
        if(mp[seq[i]]) return 0;
        else mp[seq[i]]=1;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int ma=-1;
  for(int i=0;i<n;i++) ma=max(gondolaSeq[i],ma);
  int permu=1;
  for(int i=0;i<n;i++)
  {
    if(gondolaSeq[i]<=n)
    {
        permu=(gondolaSeq[i]-i+n)%n;
    }
  }
  int gondo[250010]={};
  for(int i=0;i<n;i++) gondo[gondolaSeq[i]]=(i+n-1+permu)%n+1;
  int onpath[250010]={};
  for(int i=1;i<=n;i++) onpath[i]=i;
  int temp=gondo[ma];
  for(int i=n+1;i<=ma;i++)
  {
    if(gondo[i])
    {
        replacementSeq[i-n-1]=onpath[gondo[i]];
        onpath[gondo[i]]=i;
    }
    else
    {
        replacementSeq[i-n-1]=onpath[temp];
        onpath[temp]=i;
    }
  }
  return ma-n;
}

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

ll big=1000000009;

ll expo(int x,int y)
{
    if(y==0) return 1ll;
    if(y==1) return (long long)x;
    if(y&1) return ((((expo(x,y>>1))*(expo(x,y>>1)))%big)*(long long)x)%big;
    return ((expo(x,y>>1))*(expo(x,y>>1)))%big;
}

ll facto(int m)
{
    if(m<=1) return 1ll;
    return ((long long)m*facto(m-1))%big;
}
int countReplacement(int n, int inputSeq[])
{
    ll res=1;
    if(!valid(n,inputSeq))  return 0;
    bool ch=false;
    int ti[n];
    for(int i=0;i<n;i++)
    {
        ti[i]=inputSeq[i];
        if(ti[i]<=n) ch=true;
    }
    sort(ti,ti+n);
    for(int i=n-1;i>=0;i--)
    {
        if(ti[i]<=n) break;
        if(i) res*=expo(n-i,ti[i]-max(ti[i-1],n)-1);
        else res*=expo(n,ti[0]-n-1);
        res%=big;
    }
    if(!ch)
    {
        res*=facto(n);
        res%=big;
    }
    return (int)res;
}

• 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