Submission #638392

#	Time	Username	Problem	Language	Result	Execution time	Memory
638392		ggoh	Gondola (IOI14_gondola)	C++14	100 / 100	28 ms	3488 KiB

gondola

#include<gondola.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
lint X=1e9+9;
lint po(lint p,int q)
{
  if(q==0)return 1ll;
  if(q==1)return p;
  lint o=po(p,q/2);
  o=o*o%X;
  if(q%2)return o*p%X;
  else return o;
}
int valid(int n, int inputSeq[])
{
  vector<int>check(n+1),copy(n);
  for(int i=0;i<n;i++)
  {
    copy[i]=inputSeq[i];
    if(inputSeq[i]<=n)check[inputSeq[i]]=i+1;
  }
  sort(copy.begin(),copy.end());
  for(int i=0;i<n;i++)if(copy[i]==copy[i+1])return 0;
  int c=0,ans=1,pos,t;
  for(int i=1;i<=n;i++)
  {
    if(check[i])
    {
      if(!c)c=i,pos=check[i];
      else
      {
        t=check[i]-pos;
        if(t<=0)t+=n;
        if(t!=i-c)ans=0;
      }
    }
  }
  return ans;
}
 
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector<int>top(n),ans;
  int c=0,pos;
  for(int i=0;i<n;i++)
  {
    if(gondolaSeq[i]<=n)
    {
      c=gondolaSeq[i];
      pos=i;
    }
  }
  int left=0;
  if(c)
  {
    left=pos-(c-1);
  }
  vector<pair<int,int>>newG;
  for(int i=0;i<n;i++)
  {
    top[i]=i+1;
    newG.push_back({gondolaSeq[i],(i+n-left)%n});
  }
  sort(newG.begin(),newG.end());
  int t=n+1;
  for(auto &k:newG)
  {
    if(top[k.second]==k.first)continue;
    ans.push_back(top[k.second]);
    top[k.second]=t;
    t++;
    while(top[k.second]!=k.first)
    {
      ans.push_back(top[k.second]);
      top[k.second]++;
      t++;
    }
  }
  int sz=(int)ans.size();
  for(int i=0;i<sz;i++)replacementSeq[i]=ans[i];
  return sz;
}
 
 
int countReplacement(int n, int inputSeq[])
{
  if(!valid(n,inputSeq))return 0;
  lint ans=1ll,mul;
  vector<int>top(n);
  int c=0,pos;
  for(int i=0;i<n;i++)
  {
    if(inputSeq[i]<=n)
    {
      c=inputSeq[i];
      pos=i;
    }
  }
  int left=0;
  if(c)
  {
    left=pos-(c-1);
  }
  else ans=n;
  vector<pair<int,int>>newG;
  for(int i=0;i<n;i++)
  {
    top[i]=i+1;
    newG.push_back({inputSeq[i],(i+n-left)%n});
  }
  mul=n;
  sort(newG.begin(),newG.end());
  int t=n+1;
  for(auto &k:newG)
  {
    if(k.first==k.second+1)mul--;
    else
    {
      ans*=po(mul,k.first-t);
      ans%=X;
      t=k.first+1;
      mul--;
    }
  }
  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