oj.uz

Submission #547232

# Submission time Handle Problem Language Result Execution time Memory
547232 2022-04-09T22:10:46 Z Hanksburger Gondola (IOI14_gondola) C++17
100 / 100
 27 ms 4516 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000009;
long long sorted[100005], pos[250005];
vector<long long> vec;
long long power(long long a, long long b)
{
	if (!b)
		return 1;
	long long res=power(a, b/2);
	if (b&1)
		return res*res%mod*a%mod;
	else
		return res*res%mod;
}
int valid(int n, int a[])
{
	for (int i=0; i<n; i++)
		sorted[i]=a[i];
	sort(sorted, sorted+n);
	for (int i=1; i<n; i++)
		if (sorted[i-1]==sorted[i])
			return 0;
	for (int i=0; i<n; i++)
	{
		if (a[i]<=n)
		{
			for (int j=i+1; j<i+n; j++)
				if (a[j%n]<=n && a[j%n]!=(a[i]+j-i-1)%n+1)
					return 0;
			return 1;
		}
	}
	return 1;
}
int replacement(int n, int a[], int b[])
{
	int num=1, maxi=n;
	for (int i=0; i<n; i++)
	{
		if (a[i]<=n)
		{
			num=(n+a[i]-i-1)%n+1;
			break;
		}
	}
	for (int i=0; i<n; i++)
	{
		maxi=max(maxi, a[i]);
		pos[a[i]]=i+1;
	}
	for (int i=n+1; i<=maxi; i++)
	{
		int index=i;
		while (!pos[i])
			i++;
		vec.push_back((num+pos[i]-2)%n+1);
		for (int j=index; j<i; j++)
			vec.push_back(j);
	}
	for (int i=0; i<vec.size(); i++)
		b[i]=vec[i];
	return vec.size();
}
int countReplacement(int n, int a[])
{
	if (!valid(n, a))
		return 0;
	long long num=0, ans=1;
	for (long long i=0; i<n; i++)
	{
		if (a[i]<=n)
		{
			num=(n+a[i]-i-1)%n+1;
			break;
		}
	}
	if (!num)
	{
		ans=n;
		num=1;
	}
	vec.push_back(n);
	for (long long i=0; i<n; i++)
		if (a[i]>n)
			vec.push_back(a[i]);
	sort(vec.begin(), vec.end());
	for (long long i=1; i<vec.size(); i++)
		ans=(ans*power(vec.size()-i, vec[i]-vec[i-1]-1))%mod;
	return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i=0; i<vec.size(); i++)
      |                ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:89:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (long long i=1; i<vec.size(); i++)
      |                      ~^~~~~~~~~~~

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 1 ms 212 KB Output is correct
4 Correct 1 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 6 ms 724 KB Output is correct
7 Correct 12 ms 1344 KB Output is correct
8 Correct 9 ms 1108 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 17 ms 1236 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 1 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 7 ms 724 KB Output is correct
7 Correct 13 ms 1348 KB Output is correct
8 Correct 10 ms 1156 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 13 ms 1296 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 6 ms 728 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 13 ms 1236 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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 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 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 7 ms 1236 KB Output is correct
12 Correct 8 ms 1364 KB Output is correct
13 Correct 11 ms 2632 KB Output is correct
14 Correct 7 ms 1108 KB Output is correct
15 Correct 27 ms 4516 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
15.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 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 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 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
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 17 ms 1816 KB Output is correct
10 Correct 13 ms 1668 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 7 ms 980 KB Output is correct
13 Correct 2 ms 468 KB Output is correct

Subtask #10
10.0 / 10.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 Correct 1 ms 292 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 17 ms 1812 KB Output is correct
10 Correct 14 ms 1668 KB Output is correct
11 Correct 5 ms 980 KB Output is correct
12 Correct 8 ms 980 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 22 ms 2452 KB Output is correct
15 Correct 27 ms 3464 KB Output is correct
16 Correct 6 ms 980 KB Output is correct
17 Correct 24 ms 2248 KB Output is correct
18 Correct 10 ms 1728 KB Output is correct