제출 #838396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838396		MohamedAhmed04	곤돌라 (IOI14_gondola)	C++14	100 / 100	38 ms	6664 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 ;
	}
	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 = 1 ;
	vector<int>v ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(arr[i] > n)
			v.push_back(arr[i]) ;
	}
	sort(v.begin() , v.end()) ;
	int prv = n ;
	for(auto &x : v)
	{
		ans = Mul(ans , powlog(cnt , x - prv - 1)) ;
		cnt-- , prv = x ;
	}
	if(v.size() == n)
		ans = Mul(ans , n) ;
	return ans ;
}

컴파일 시 표준 에러 (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 countReplacement(int, int*)':
gondola.cpp:146:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  146 |  if(v.size() == n)
      |     ~~~~~~~~~^~~~
gondola.cpp:128:6: warning: unused variable 'Max' [-Wunused-variable]
  128 |  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: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10