Submission #625904

#	Time	Username	Problem	Language	Result	Execution time	Memory
625904		as111	Gondola (IOI14_gondola)	C++14	100 / 100	20 ms	2724 KiB

gondola

#include "gondola.h"
#include <iostream>
#include <set>
#include <algorithm>
#define MOD 1000000009
 
int arr[250001];
int now[250001];

 
using namespace std;
 
int valid(int n, int inputSeq[]) {
	int start = 0;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] <= n) {
			start = i;
			break;
		}
	}
	if (start < n) {
		for (int j = 0; j < n; j++) {
			if (inputSeq[j] <= n && (inputSeq[j] + start) % n != (inputSeq[start] + j) % n) return 0;
		}
	}
	sort(inputSeq, inputSeq + n);
	for (int 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