oj.uz

Submission #129960

# Submission time Handle Problem Language Result Execution time Memory
129960 2019-07-13T16:06:44 Z tinjyu Gondola (IOI14_gondola) C++14
100 / 100
 41 ms 4992 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 1016 KB Output is correct
8 Correct 15 ms 888 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 21 ms 1144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 1016 KB Output is correct
8 Correct 15 ms 888 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 21 ms 1016 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 11 ms 692 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 21 ms 1016 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 16 ms 1912 KB Output is correct
12 Correct 18 ms 2140 KB Output is correct
13 Correct 19 ms 1784 KB Output is correct
14 Correct 16 ms 1912 KB Output is correct
15 Correct 24 ms 2424 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 32 ms 3064 KB Output is correct
10 Correct 28 ms 2552 KB Output is correct
11 Correct 11 ms 1272 KB Output is correct
12 Correct 13 ms 1404 KB Output is correct
13 Correct 4 ms 632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 32 ms 3068 KB Output is correct
10 Correct 26 ms 2556 KB Output is correct
11 Correct 11 ms 1272 KB Output is correct
12 Correct 13 ms 1400 KB Output is correct
13 Correct 4 ms 636 KB Output is correct
14 Correct 36 ms 3576 KB Output is correct
15 Correct 41 ms 4992 KB Output is correct
16 Correct 9 ms 1272 KB Output is correct
17 Correct 27 ms 3448 KB Output is correct
18 Correct 16 ms 2168 KB Output is correct