oj.uz

Submission #39142

# Submission time Handle Problem Language Result Execution time Memory
39142 2018-01-09T13:34:57 Z faustaadp Gondola (IOI14_gondola) C++14
100 / 100
 76 ms 48924 KB 
#include "gondola.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll i,a[1010101],sat,tt,mi,ma,c[1010101],e[1010101],f[1010101],hs,b[1010101],hl,mo=1000000009;
unordered_map<ll,ll> am;
vector<ll> v;
int valid(int n, int inputSeq[])
{
	for(i=0;i<n;i++)
		if(am[inputSeq[i]]==0)
			am[inputSeq[i]]++;
		else
			return 0;
	//cout<<"sd";
	mi=10e17;
	for(i=0;i<n;i++)
		if(inputSeq[i]<mi)
		{
			mi=inputSeq[i];
			sat=i;
			tt=mi-1;
		}
	for(i=sat;i<2*n;i++)
	{
		tt++;
		if(tt>n)
			tt-=n;
		if(inputSeq[i%n]<=n)
			if(inputSeq[i%n]!=tt)
			{
			//	cout<<inputSeq[i%n]<<" "<<tt<<"\n";
				return 0;
			}
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	for(i=0;i<n;i++)
		a[i]=gondolaSeq[i];
	for(i=0;i<n;i++)
		ma=max(ma,(ll)gondolaSeq[i]);
	mi=10e17;
	for(i=0;i<n;i++)
		if(gondolaSeq[i]<mi)
		{
			mi=gondolaSeq[i];
			sat=i;
			tt=mi-1;
		}
	for(i=sat;i<2*n;i++)
	{
		tt++;
		while(tt>n)
			tt-=n;
	//	cout<<i%n<<" "<<tt<<"\n";
		e[i%n]=tt;
	}
	for(i=0;i<n;i++)
	{
		c[a[i]]=e[i];
		f[i+1]=i+1;
	}
	for(i=n+1;i<=ma;i++)
	{
		if(c[i]==0)
		{
			replacementSeq[i-n-1]=f[c[ma]];
			f[c[ma]]=i;
		}
		else
		{
			replacementSeq[i-n-1]=f[c[i]];
			f[c[i]]=i;
		}
	//	cout<<i-n-1<<" "<<replacementSeq[i-n-1]<<"\n";
	}
	return ma-n;
}

//----------------------
ll powo(ll aa,ll bb)
{
	if(bb==0)
		return 1;
	else
	if(bb==1)
		return aa;
	else
	{
		ll tj=powo(aa,bb/2);
		tj*=tj;
		tj%=mo;
		if(bb%2==1)
			tj*=aa;
		tj%=mo;
		return tj;
	}
}
int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))
		return 0;
	else
	{
		hs=1;
		v.pb(n);
		for(i=0;i<n;i++)
			if(inputSeq[i]>n)
			{
			//	b[inputSeq[i]]=1;
				v.pb(inputSeq[i]);
				hl++;
			}
		for(i=0;i<n;i++)
			ma=max(ma,(ll)inputSeq[i]);
		mi=10e17;
		for(i=0;i<n;i++)
			if(inputSeq[i]<mi)
			{
				mi=inputSeq[i];
				sat=i;
				tt=mi-1;
			}
		sort(v.begin(),v.end());
		for(i=1;i<v.size();i++)
		{
			hs*=powo(hl,v[i]-v[i-1]-1);
			hs%=mo;
			hl--;
		}
		if(mi>n)
			hs*=n;
		hs%=mo;
	}
	return hs;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:131:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=1;i<v.size();i++)
            ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 42848 KB Output is correct
2 Correct 0 ms 42848 KB Output is correct
3 Correct 0 ms 42848 KB Output is correct
4 Correct 0 ms 42848 KB Output is correct
5 Correct 0 ms 42848 KB Output is correct
6 Correct 9 ms 44596 KB Output is correct
7 Correct 6 ms 42848 KB Output is correct
8 Correct 23 ms 46264 KB Output is correct
9 Correct 6 ms 43844 KB Output is correct
10 Correct 26 ms 46436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 42848 KB Output is correct
2 Correct 0 ms 42848 KB Output is correct
3 Correct 0 ms 42848 KB Output is correct
4 Correct 0 ms 42848 KB Output is correct
5 Correct 0 ms 42848 KB Output is correct
6 Correct 13 ms 44596 KB Output is correct
7 Correct 9 ms 42848 KB Output is correct
8 Correct 23 ms 46264 KB Output is correct
9 Correct 6 ms 43844 KB Output is correct
10 Correct 19 ms 46436 KB Output is correct
11 Correct 0 ms 42848 KB Output is correct
12 Correct 0 ms 42848 KB Output is correct
13 Correct 16 ms 44596 KB Output is correct
14 Correct 0 ms 42848 KB Output is correct
15 Correct 36 ms 46568 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 42848 KB Output is correct
2 Correct 0 ms 42848 KB Output is correct
3 Correct 0 ms 42848 KB Output is correct
4 Correct 0 ms 42848 KB Output is correct
5 Correct 0 ms 42848 KB Output is correct
6 Correct 0 ms 42848 KB Output is correct
7 Correct 0 ms 42848 KB Output is correct
8 Correct 0 ms 42848 KB Output is correct
9 Correct 0 ms 42848 KB Output is correct
10 Correct 0 ms 42848 KB Output is correct
11 Correct 26 ms 42848 KB Output is correct
12 Correct 26 ms 42848 KB Output is correct
13 Correct 26 ms 42848 KB Output is correct
14 Correct 13 ms 42848 KB Output is correct
15 Correct 33 ms 42848 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 42848 KB Output is correct
2 Correct 0 ms 42848 KB Output is correct
3 Correct 0 ms 42848 KB Output is correct
4 Correct 0 ms 42848 KB Output is correct
5 Correct 0 ms 42848 KB Output is correct
6 Correct 0 ms 42848 KB Output is correct
7 Correct 0 ms 42848 KB Output is correct
8 Correct 0 ms 42848 KB Output is correct
9 Correct 39 ms 47236 KB Output is correct
10 Correct 39 ms 46224 KB Output is correct
11 Correct 13 ms 44252 KB Output is correct
12 Correct 16 ms 44408 KB Output is correct
13 Correct 3 ms 43316 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 42848 KB Output is correct
2 Correct 0 ms 42848 KB Output is correct
3 Correct 0 ms 42848 KB Output is correct
4 Correct 0 ms 42848 KB Output is correct
5 Correct 0 ms 42848 KB Output is correct
6 Correct 0 ms 42848 KB Output is correct
7 Correct 0 ms 42848 KB Output is correct
8 Correct 0 ms 42848 KB Output is correct
9 Correct 56 ms 47236 KB Output is correct
10 Correct 19 ms 46224 KB Output is correct
11 Correct 16 ms 44252 KB Output is correct
12 Correct 26 ms 44408 KB Output is correct
13 Correct 3 ms 43316 KB Output is correct
14 Correct 66 ms 48584 KB Output is correct
15 Correct 76 ms 48924 KB Output is correct
16 Correct 16 ms 44116 KB Output is correct
17 Correct 46 ms 46928 KB Output is correct
18 Correct 29 ms 45436 KB Output is correct