Submission #838394

#	Time	Username	Problem	Language	Result	Execution time	Memory
838394		MohamedAhmed04	Gondola (IOI14_gondola)	C++14	60 / 100	25 ms	5328 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std ;

const int MAX = 3e5 + 10 ;

int arr[MAX] ;

int valid(int n, int inputSeq[])
{
	for(int i = 0 ; i < 2*n ; ++i)
		arr[i] = inputSeq[i%n] ;
	set<int>s ;
	for(int i = 0 ; i < n ; ++i)
		s.insert(arr[i]) ;
	if(s.size() != n)
		return 0 ;
	int idx = -1 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] <= n)
			idx = i ;
	}
	if(idx == -1)
		return 1 ;
	int now = arr[idx]-1 ;
	for(int i = idx ; i < idx+n ; ++i)
	{
		++now ;
		if(now == n+1)
			now = 1 ;
		if(arr[i] != now && arr[i] <= n)
			return 0 ;
	}
	return 1 ;
}

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

int mark[MAX] ;

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	for(int i = 0 ; i < 2*n ; ++i)
		arr[i] = gondolaSeq[i%n] ;
	int idx = -1 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] <= n)
			idx = i ;
	}
	int Max = *max_element(arr , arr + n) ;
	for(int i = 0 ; i < n ; ++i)
		mark[arr[i]] = 1 ;
	vector< pair<int , int> >vp ;
	if(idx == -1)
	{
		for(int i = 0 ; i < n ; ++i)
			vp.emplace_back(arr[i] , i+1) ;
	}
	else
	{
		int now = arr[idx] - 1 ;
		for(int i = idx ; i < idx+n ; ++i)
		{
			++now ;
			if(now == n+1)
				now = 1 ;
			if(arr[i] > n)
				vp.emplace_back(arr[i] , now) ;
		}
	}
	sort(vp.begin() , vp.end()) ;
	idx = 0 ;
	int prv = n ;
	for(auto &p : vp)
	{
		replacementSeq[idx] = p.second , ++idx ;
		for(int i = prv+1 ; i < p.first ; ++i)
			replacementSeq[idx] = i , ++idx ;
		prv = p.first ;
	}
	return idx ;
}

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

const int mod = 1e9 + 9 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Sub(int x , int y)
{
	int z = x - y ;
	if(z < 0)
		z += mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (1ll * x * y) % mod ;
}

int powlog(int base , int power)
{
	if(power == 0)
		return 1 ;
	int x = powlog(base , power / 2) ;
	x = Mul(x , x) ;
	if(power & 1)
		x = Mul(x , base) ;
	return x ;
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n , inputSeq))
		return 0 ;
	for(int i = 0 ; i < 2*n ; ++i)
		arr[i] = inputSeq[i%n] ;
	int Max = *max_element(arr , arr + n) ;
	int cnt = 0 ;
	for(int i = 0 ; i < n ; ++i)
		cnt += (arr[i] > n) ;
	int ans = powlog(cnt , Max - n - cnt) ;
	if(cnt == n)
		ans = Mul(ans , n) ;
	return ans ;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:17:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |  if(s.size() != n)
      |     ~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:53:6: warning: unused variable 'Max' [-Wunused-variable]
   53 |  int Max = *max_element(arr , arr + n) ;
      |      ^~~

• 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10