oj.uz

Submission #53122

# Submission time Handle Problem Language Result Execution time Memory
53122 2018-06-28T12:48:17 Z zetapi Gondola (IOI14_gondola) C++14
65 / 100
 124 ms 9008 KB 
#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
const int MAX=1e6;
const ll mod=1e9+9;
 
int arr[MAX];

map<ll,ll> fre;
 
ll power(ll base,ll exp)
{
	ll res=1;
	while(exp)
	{
		if(exp%2)
			res*=base;
		base*=base;
		res%=mod;
		base%=mod;
		exp/=2;
	}
	return res;
}
 
int valid(int n, int inputSeq[])
{
  	int N=n,ok=1;
	for(int A=0;A<N;A++)
	{
		fre[inputSeq[A]]++;
		if(fre[inputSeq[A]]>1)
		 	return 0;
	}
  	for(int A=0;A<N;A++)
  	{
  	  	if(inputSeq[A]<=N)
  	  	{	
		 	ok=0;
		 	inputSeq[A]--;
		 	for(int B=A;B>=0;B--)
		 	{
			 	arr[B]=inputSeq[A];
			 	inputSeq[A]--;
			 	if(inputSeq[A]<0)
			 		inputSeq[A]+=N;
		 	}
		 	inputSeq[A]=arr[A];
		 	for(int B=A+1;B<N;B++)
		 	{
		 		inputSeq[A]++;
		 		if(inputSeq[A]>=N)
		 			inputSeq[A]=0;
		 		arr[B]=inputSeq[A];
		 	}
		 	inputSeq[A]=arr[A]+1;
		 	break;
	  	}
  	}
  	if(ok)
  	 	return 1;
  	for(int A=0;A<N;A++)
  	 	arr[A]++;
  	for(int A=0;A<N;A++)
  	{
  	  	if(inputSeq[A]<=N and arr[A]!=inputSeq[A])
  	  		return 0;	
  	}
  	return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  	return -2;
}
 
//----------------------
 
//long long
int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))
		return 0;
	sort(inputSeq,inputSeq+n);
	vector<ll> vec;
	for(int A=0;A<n;A++)
		if(inputSeq[A]>n)
			vec.push_back(inputSeq[A]);
	if(vec.empty())
		return 1;
	sort(vec.begin(),vec.end());
	ll res=1,ptr=0,cnt=vec.size();
	while(ptr<n and inputSeq[ptr]<=n)
		++ptr;
	for(int A=0;A<vec.size()-1;A++)
	{
		while(ptr<n and inputSeq[ptr]<=vec[A])
			++ptr,--cnt;
		//cout<<ptr<<"\n";
		//cout<<vec[A]<<" "<<cnt<<"\n";
		if(vec[A+1]-vec[A]>1)
		{
			res*=power(cnt,vec[A+1]-vec[A]-1);
			res%=mod;
		}
	}
	if(vec[0]!=n+1)
	{
		res*=power((ll)vec.size(),(vec[0]-n-1));
		res%=mod;
	}
	if(inputSeq[0]>n)
	{
		res*=(ll)n;
		res%=mod;
	}
	return res;
}
 
/*signed main()
{
	ios_base::sync_with_stdio(false);
	
	int arr[]={3,4};
	cout<<countReplacement(2,arr);
	return 0;
}*/

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<vec.size()-1;A++)
              ~^~~~~~~~~~~~~

Subtask #1
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 412 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 3 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 22 ms 3068 KB Output is correct
7 Correct 14 ms 3068 KB Output is correct
8 Correct 46 ms 5504 KB Output is correct
9 Correct 14 ms 5504 KB Output is correct
10 Correct 56 ms 6332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6332 KB Output is correct
2 Correct 2 ms 6332 KB Output is correct
3 Correct 3 ms 6332 KB Output is correct
4 Correct 3 ms 6332 KB Output is correct
5 Correct 3 ms 6332 KB Output is correct
6 Correct 23 ms 6332 KB Output is correct
7 Correct 14 ms 6332 KB Output is correct
8 Correct 63 ms 6332 KB Output is correct
9 Correct 14 ms 6332 KB Output is correct
10 Correct 54 ms 6380 KB Output is correct
11 Correct 2 ms 6380 KB Output is correct
12 Correct 2 ms 6380 KB Output is correct
13 Correct 25 ms 6380 KB Output is correct
14 Correct 2 ms 6380 KB Output is correct
15 Correct 103 ms 6648 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6648 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6648 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6648 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6648 KB Output is correct
2 Correct 2 ms 6648 KB Output is correct
3 Correct 2 ms 6648 KB Output is correct
4 Correct 2 ms 6648 KB Output is correct
5 Correct 3 ms 6648 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6648 KB Output is correct
8 Correct 2 ms 6648 KB Output is correct
9 Correct 61 ms 6648 KB Output is correct
10 Correct 48 ms 6648 KB Output is correct
11 Correct 18 ms 6648 KB Output is correct
12 Correct 22 ms 6648 KB Output is correct
13 Correct 6 ms 6648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6648 KB Output is correct
2 Correct 2 ms 6648 KB Output is correct
3 Correct 2 ms 6648 KB Output is correct
4 Correct 2 ms 6648 KB Output is correct
5 Correct 2 ms 6648 KB Output is correct
6 Correct 2 ms 6648 KB Output is correct
7 Correct 2 ms 6648 KB Output is correct
8 Correct 2 ms 6648 KB Output is correct
9 Correct 69 ms 6648 KB Output is correct
10 Correct 48 ms 6648 KB Output is correct
11 Correct 26 ms 6648 KB Output is correct
12 Correct 23 ms 6648 KB Output is correct
13 Correct 7 ms 6648 KB Output is correct
14 Correct 98 ms 7352 KB Output is correct
15 Correct 124 ms 9008 KB Output is correct
16 Correct 21 ms 9008 KB Output is correct
17 Correct 56 ms 9008 KB Output is correct
18 Correct 31 ms 9008 KB Output is correct