oj.uz

Submission #838395

# Submission time Handle Problem Language Result Execution time Memory
838395 2023-08-26T18:55:50 Z MohamedAhmed04 Gondola (IOI14_gondola) C++14
60 / 100
 31 ms 5288 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 ;
	}
	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

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.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 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 0 ms 212 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 20 ms 4364 KB Output is correct
8 Correct 15 ms 4400 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 20 ms 5104 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 10 ms 2516 KB Output is correct
7 Correct 21 ms 4328 KB Output is correct
8 Correct 15 ms 4436 KB Output is correct
9 Correct 5 ms 1544 KB Output is correct
10 Correct 20 ms 5076 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 10 ms 2260 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 31 ms 5288 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 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 #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 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 0 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 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 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 7 ms 1492 KB Output is correct
12 Correct 8 ms 1620 KB Output is correct
13 Correct 11 ms 1892 KB Output is correct
14 Correct 7 ms 1460 KB Output is correct
15 Correct 19 ms 2892 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
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 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.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 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.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 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -