oj.uz

Submission #53124

# Submission time Handle Problem Language Result Execution time Memory
53124 2018-06-28T12:50:22 Z zetapi Gondola (IOI14_gondola) C++14
100 / 100
 164 ms 16704 KB 
#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
 
 #define pb  push_back
#define mp  make_pair
#define ll long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
const int MAX=1e6;
const ll mod=1e9+9;
 
int arr[MAX],fin[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;
}*/
 
 
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
	vector<int> vec;
	priority_queue<int> absent;
	priority_queue<pii> present;
	pii cur;
	int N=n,mx=0,change=0,sec;
	for(int A=0;A<N;A++)
		arr[A]=A;
	for(int A=0;A<N;A++)
  	{
	  	if(gondolaSeq[A]<=N)
	  	{
			 gondolaSeq[A]--;
			 for(int B=A;B>=0;B--)
			 {
			 	arr[B]=gondolaSeq[A];
			 	gondolaSeq[A]--;
			 	if(gondolaSeq[A]<0)
			 		gondolaSeq[A]+=N;
			 }
			 gondolaSeq[A]=arr[A];
			 for(int B=A+1;B<N;B++)
			 {
			 	gondolaSeq[A]++;
			 	if(gondolaSeq[A]>=N)
			 		gondolaSeq[A]=0;
			 	arr[B]=gondolaSeq[A];
			 }
			 gondolaSeq[A]=arr[A]+1;
		 	 break;
		}
  	}
  	for(int A=0;A<N;A++)
  		arr[A]++;
  	for(int A=0;A<N;A++)
  	{
  		fre[gondolaSeq[A]]++;
  		mx=max(mx,gondolaSeq[A]);
  		present.push(mp(gondolaSeq[A],A));
  		if(arr[A]!=gondolaSeq[A])
  			change++;
  	}
  	for(int A=1;A<=mx;A++)
  	{
  		if(!fre[A])
  			absent.push(A);
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		if(cur.first<=N+change)
  			break;
  		present.pop();
  		sec=absent.top();
  		present.push(mp(sec,cur.second));
  		absent.pop();
  		//cout<<cur.second<<" "<<cur.first<<" "<<sec<<"\n";
  		vec.pb(sec);
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		present.pop();	
  		fin[cur.second]=cur.first;
  	}
  	for(int A=0;A<N;A++)
  	{
  		if(fin[A]!=arr[A])
  			present.push(mp(fin[A],arr[A]));
  	}
  	while(!present.empty())
  	{
  		cur=present.top();
  		present.pop();
  		vec.pb(cur.second);
  	}
  	reverse(vec.begin(),vec.end());
  //	for(auto A:vec)
  	//	cout<<A<<" ";
  	for(int A=0;A<vec.size();A++)
  		replacementSeq[A]=vec[A];
  	return vec.size();
}
//----------------------
 
//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 replacement(int, int*, int*)':
gondola.cpp:168:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<vec.size();A++)
                ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:190: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 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 460 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 2 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 32 ms 3132 KB Output is correct
7 Correct 27 ms 3132 KB Output is correct
8 Correct 45 ms 5588 KB Output is correct
9 Correct 13 ms 5588 KB Output is correct
10 Correct 52 ms 6384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6384 KB Output is correct
2 Correct 2 ms 6384 KB Output is correct
3 Correct 1 ms 6384 KB Output is correct
4 Correct 2 ms 6384 KB Output is correct
5 Correct 2 ms 6384 KB Output is correct
6 Correct 22 ms 6384 KB Output is correct
7 Correct 14 ms 6384 KB Output is correct
8 Correct 45 ms 6384 KB Output is correct
9 Correct 13 ms 6384 KB Output is correct
10 Correct 52 ms 6396 KB Output is correct
11 Correct 2 ms 6396 KB Output is correct
12 Correct 2 ms 6396 KB Output is correct
13 Correct 24 ms 6396 KB Output is correct
14 Correct 2 ms 6396 KB Output is correct
15 Correct 58 ms 6652 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6652 KB Output is correct
2 Correct 2 ms 6652 KB Output is correct
3 Correct 2 ms 6652 KB Output is correct
4 Correct 3 ms 6652 KB Output is correct
5 Correct 2 ms 6652 KB Output is correct
6 Correct 2 ms 6652 KB Output is correct
7 Correct 3 ms 6652 KB Output is correct
8 Correct 5 ms 6652 KB Output is correct
9 Correct 4 ms 6652 KB Output is correct
10 Correct 4 ms 6652 KB Output is correct
11 Correct 57 ms 7828 KB Output is correct
12 Correct 69 ms 9132 KB Output is correct
13 Correct 80 ms 10420 KB Output is correct
14 Correct 60 ms 10420 KB Output is correct
15 Correct 164 ms 16704 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16704 KB Output is correct
2 Correct 2 ms 16704 KB Output is correct
3 Correct 2 ms 16704 KB Output is correct
4 Correct 2 ms 16704 KB Output is correct
5 Correct 2 ms 16704 KB Output is correct
6 Correct 2 ms 16704 KB Output is correct
7 Correct 2 ms 16704 KB Output is correct
8 Correct 2 ms 16704 KB Output is correct
9 Correct 60 ms 16704 KB Output is correct
10 Correct 47 ms 16704 KB Output is correct
11 Correct 19 ms 16704 KB Output is correct
12 Correct 21 ms 16704 KB Output is correct
13 Correct 9 ms 16704 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16704 KB Output is correct
2 Correct 2 ms 16704 KB Output is correct
3 Correct 2 ms 16704 KB Output is correct
4 Correct 2 ms 16704 KB Output is correct
5 Correct 2 ms 16704 KB Output is correct
6 Correct 2 ms 16704 KB Output is correct
7 Correct 2 ms 16704 KB Output is correct
8 Correct 2 ms 16704 KB Output is correct
9 Correct 105 ms 16704 KB Output is correct
10 Correct 50 ms 16704 KB Output is correct
11 Correct 19 ms 16704 KB Output is correct
12 Correct 28 ms 16704 KB Output is correct
13 Correct 7 ms 16704 KB Output is correct
14 Correct 102 ms 16704 KB Output is correct
15 Correct 94 ms 16704 KB Output is correct
16 Correct 14 ms 16704 KB Output is correct
17 Correct 58 ms 16704 KB Output is correct
18 Correct 30 ms 16704 KB Output is correct