Submission #129960

#	Time	Username	Problem	Language	Result	Execution time	Memory
129960		tinjyu	Gondola (IOI14_gondola)	C++14	100 / 100	41 ms	4992 KiB

gondola

#include "gondola.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long int ans[1000005];
long long int a[1000005],b[1000005],n;
struct node{
	int a,b;
}c[100005];
bool cmp(node x,node y)
{
	return x.a<y.a;
}
int qs(int s,int e)
{
	if(s>=e)return 0;
	long long int l=s,r=e,mid=(a[l]+a[r])/2;
	while(l<=r)
	{
		while(a[l]<mid)l++;
		while(a[r]>mid)r--;
		if(l<=r)
		{
			swap(a[l],a[r]);
			swap(b[l],b[r]);
			l++;
			r--;
		}
	}
	qs(s,r);
	qs(l,e);
}
int valid(int N, int a[])
{
	n=N;
	int tmp=-1,mi=500005,tag[500005];
	int d[100005];
	for(int i=0;i<n;i++)d[i]=a[i];
	sort(d,d+n);
	for(int i=0;i<n-1;i++)
	{
		if(d[i]==d[i+1])return 0;
	}
	for(int i=0;i<n;i++)
	if(a[i]<=n && a[i]<mi)
	{
		tmp=i;
		mi=a[i];
	}
	if(tmp==-1)return 1;
	int p=n-1,i=tmp,t=mi;
	while(p--)
	{
		i++;
		i%=n;
		t++;
		if(a[i]<=n && a[i]!=t)return 0;
	}
 
	return 1;
}
 

//----------------------
 
int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
	n=N;
	int t=-1;
	for(int i=0;i<n;i++)a[i]=gondolaSeq[i];
	for(int i=0;i<n;i++)
	{
		if(a[i]<=n)
		{
			t=i;
			break;
		}
	}
	if(t==-1)for(int i=0;i<n;i++)b[i]=i+1;
	else
	{
		b[t]=a[t];
		int now=a[t],i=t;
		int p=n-1;
		while(p--)
		{
			i++;
			i%=n;
			now=now%n+1;
			b[i]=now;
		}
	}
	//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
	qs(0,n-1);
	//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
	int ans1=0,x=n+1;
	for(int i=0;i<n;i++)
	{
		while(a[i]!=b[i])
		{
			
			replacementSeq[ans1]=b[i];
			b[i]=x;
			ans1++;
			x++;
		}
	}
  	return ans1;
}
 
//----------------------
 
int countReplacement(int N, int inputSeq[])
{
	if(valid(N,inputSeq)==0)return 0;
	n=N;
	int t=-1;
	for(int i=0;i<n;i++)c[i].a=inputSeq[i];
	for(int i=0;i<n;i++)
	{
		if(c[i].a<=n)
		{
			t=i;
			break;
		}
	}	

	long long int ans1=1,x=n+1,tmp;
	if(t==-1)
	{
		for(int i=0;i<n;i++)c[i].b=i+1;
		ans1=(ans1*n)%1000000009;
	}
	else
	{
		c[t].b=c[t].a;
		long long int now=c[t].a,i=t;
		long long int p=n-1;
		while(p--)
		{
			i++;
			i%=n;
			now=now%n+1;
			c[i].b=now;
		}
	}
	//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
	sort(c,c+n,cmp);

	//for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;
	for(int i=0;i<n;i++)
	{
		a[i]=c[i].a;
		b[i]=c[i].b;
	}
	
	for(long long int i=0;i<n;i++)
	{
		int tmp=0;
		if(a[i]!=b[i])
		{
			tmp=a[i]-x+1;
			x=a[i]+1;
		}
		if(tmp!=0)
		{
			ans[0]++;
			ans[ans[0]]=tmp;
		}
	}
	for(long long int i=1;i<=ans[0];i++)
	{
		//cout<<ans[i]<<" ";
		long long int p=ans[i]-1,x=(ans[0]-i+1);
		while(p>0)
		{
			if(p%2==1)ans1=(ans1*x)%1000000009;
			p/=2;
			x=(x*x)%1000000009;
		}
		
	}
  	return ans1;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:36:23: warning: unused variable 'tag' [-Wunused-variable]
  int tmp=-1,mi=500005,tag[500005];
                       ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:128:29: warning: unused variable 'tmp' [-Wunused-variable]
  long long int ans1=1,x=n+1,tmp;
                             ^~~
gondola.cpp: In function 'int qs(int, int)':
gondola.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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