oj.uz

Submission #838396

# Submission time Handle Problem Language Result Execution time Memory
838396 2023-08-26T19:01:30 Z MohamedAhmed04 Gondola (IOI14_gondola) C++14
100 / 100
 38 ms 6664 KB 
#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 ;
}

Compilation message

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.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 8 ms 2408 KB Output is correct
7 Correct 20 ms 4308 KB Output is correct
8 Correct 15 ms 4480 KB Output is correct
9 Correct 5 ms 1648 KB Output is correct
10 Correct 23 ms 5108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 21 ms 4340 KB Output is correct
8 Correct 15 ms 4436 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 19 ms 5184 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 9 ms 2260 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 24 ms 5332 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 1492 KB Output is correct
12 Correct 7 ms 1620 KB Output is correct
13 Correct 12 ms 1920 KB Output is correct
14 Correct 7 ms 1492 KB Output is correct
15 Correct 17 ms 2856 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 26 ms 4972 KB Output is correct
10 Correct 26 ms 4288 KB Output is correct
11 Correct 8 ms 1748 KB Output is correct
12 Correct 10 ms 2100 KB Output is correct
13 Correct 2 ms 724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 27 ms 5080 KB Output is correct
10 Correct 21 ms 4180 KB Output is correct
11 Correct 8 ms 1728 KB Output is correct
12 Correct 13 ms 2004 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 33 ms 6024 KB Output is correct
15 Correct 38 ms 6664 KB Output is correct
16 Correct 6 ms 1520 KB Output is correct
17 Correct 24 ms 4576 KB Output is correct
18 Correct 16 ms 2752 KB Output is correct