oj.uz

Submission #430370

# Submission time Handle Problem Language Result Execution time Memory
430370 2021-06-16T13:12:00 Z frodakcin Gondola (IOI14_gondola) C++11
100 / 100
 86 ms 5956 KB 
#include "gondola.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <algorithm>

int valid(int n, int inputSeq[])
{
	std::map<int, int> map;
	for(int i=0;i<n;++i)
	{
		int x=inputSeq[i]-1;
		if(map.find(x) != map.end()) return 0;
		map.insert({x, i});
	}
	for(int i=0;i<n;++i)
		if(map.find(i)!=map.end() && map.find((i+1)%n)!=map.end())
		{
			int u=map[i], v=map[(i+1)%n];
			if(v != (u+1)%n)
				return 0;
		}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	for(int i=0;i<n;++i)
		if(gondolaSeq[i] <= n && gondolaSeq[i] != i+1)
		{
			std::rotate(gondolaSeq, gondolaSeq+(i-gondolaSeq[i]+1+n)%n, gondolaSeq+n);
		}
	std::map<int, int> map;
	for(int i=0;i<n;++i)
	{
		int x=gondolaSeq[i];
		assert(map.find(x) == map.end());
		map.insert({x, i});
	}
	int l=0, v=n;
	for(auto x:map)
		for(int t=x.second+1;v<x.first;)
			replacementSeq[l++]=t, t=++v;
	return l;
}

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

using ll = long long;
const int MOD = 1e9+9;

struct mint
{
	public:
		int v;
		mint(int _v=0): v(_v)
		{
			if(v < -MOD || MOD <= v) v%=MOD;
			if(v<0) v+=MOD;
		}

		mint& operator += (const mint& o) {if((v+=o.v)>=MOD) v-=MOD; return *this;}
		mint& operator -= (const mint& o) {if((v-=o.v)<0) v+=MOD;return *this;}
		mint& operator *= (const mint& o) {v=(ll)v*o.v%MOD; return *this;}

		friend mint operator + (mint a, const mint& b) {return a+=b;}
		friend mint operator - (mint a, const mint& b) {return a-=b;}
		friend mint operator * (mint a, const mint& b) {return a*=b;}

		template<typename T>
		friend mint pow(mint b, T p)
		{
			mint f(1);
			for(;p;p>>=1, b*=b)
				if(p&1)
					f*=b;
			return f;
		}
};

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq)) return 0;
	std::sort(inputSeq, inputSeq+n);
	mint ans(1);
	if(inputSeq[0] > n)
		ans *= mint(n);

	int v=n;
	for(int i=0;i<n;++i)
	{
		if(v < inputSeq[i])
			ans *= pow(mint(n-i), inputSeq[i]-v-1), v=inputSeq[i];
	}

	return ans.v;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 31 ms 2204 KB Output is correct
7 Correct 14 ms 588 KB Output is correct
8 Correct 64 ms 3908 KB Output is correct
9 Correct 19 ms 1376 KB Output is correct
10 Correct 75 ms 4496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 34 ms 2184 KB Output is correct
7 Correct 15 ms 592 KB Output is correct
8 Correct 58 ms 3844 KB Output is correct
9 Correct 18 ms 1348 KB Output is correct
10 Correct 76 ms 4504 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 23 ms 1996 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 56 ms 4584 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 38 ms 4216 KB Output is correct
12 Correct 48 ms 4784 KB Output is correct
13 Correct 33 ms 2684 KB Output is correct
14 Correct 44 ms 4248 KB Output is correct
15 Correct 36 ms 2788 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 236 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 62 ms 4484 KB Output is correct
10 Correct 48 ms 3752 KB Output is correct
11 Correct 17 ms 1640 KB Output is correct
12 Correct 21 ms 1928 KB Output is correct
13 Correct 4 ms 588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 53 ms 4488 KB Output is correct
10 Correct 51 ms 3756 KB Output is correct
11 Correct 16 ms 1460 KB Output is correct
12 Correct 17 ms 1856 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 58 ms 5288 KB Output is correct
15 Correct 86 ms 5956 KB Output is correct
16 Correct 13 ms 1336 KB Output is correct
17 Correct 47 ms 4028 KB Output is correct
18 Correct 30 ms 2360 KB Output is correct