oj.uz

Submission #168545

# Submission time Handle Problem Language Result Execution time Memory
168545 2019-12-13T15:46:37 Z johutha Gondola (IOI14_gondola) C++14
65 / 100
 22 ms 2404 KB 
#include "gondola.h"
#include <vector>
#include <algorithm>
#include <iostream>

#define int int64_t

using namespace std;

const int mod = 1000000009;

signed fastpowmod(int base, int exp)
{
	int res = 1;
	for (; exp; exp /= 2)
	{
		if (exp & 1) res = (res*base) % mod;
		base *= base;
	}

	return res;
}

signed valid(signed n, signed inputSeq[])
{
	for (int i = 0; i < n; i++) inputSeq[i]--;

	int zval = 0;
	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] < n)
		{
			zval = inputSeq[i] - i;
			break;
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (inputSeq[i] < n)
		{
			if ((zval + i + n) % n != inputSeq[i]) return 0;
		}
	}

	return 1;
}

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

signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[])
{
	vector<int> Seq;
	
	for (int i = 0; i < n; i++) Seq.push_back(gondolaSeq[i] - 1);

	int zval = 0;
	for (int i = 0; i < n; i++)
	{
		if (Seq[i] < n)
		{
			zval = Seq[i] - i;
			break;
		}
	}

	rotate(Seq.rbegin(), Seq.rbegin() + ((zval + n) % n), Seq.rend());
	int mmax = *max_element(Seq.begin(), Seq.end());
	int mind = -1;

	for (int i = 0; i <= mmax - n; i++) replacementSeq[i] = -1;

	for (int i = 0; i < n; i++)
	{
		if (Seq[i] == mmax) mind = i;
		if (Seq[i] >= n) replacementSeq[Seq[i] - n] = i + 1;
	}

	mind++;
	for (int i = 0; i <= mmax - n; i++)
	{
		if (replacementSeq[i] == -1)
		{
			replacementSeq[i] = mind;
			mind = n + i + 1;
		}
	}
	replacementSeq[mmax - n] = mind;

	return mmax - n + 1;
}

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

signed countReplacement(signed n, signed inputSeq[])
{
	if (!valid(n, inputSeq)) return 0;
	
	vector<int> Seq;

	for (int i = 0; i < n; i++) Seq.push_back(inputSeq[i]);

  	sort(Seq.begin(), Seq.end());

	int last = n - 1;
	int res = 1;

	bool defined = false;

	for (int i = 0; i < n; i++)
	{
		if (Seq[i] < n)
		{
			defined = true;
			continue;
		}
		int len = Seq[i] - last - 1;
		last = Seq[i];
		res = (res * fastpowmod(n - i, len)) % mod;
	}

	if (!defined)
	{
		for (int i = 1; i <= n; i++)
		{
			res = (res * i) % mod;
		}
	}

	return res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 13 ms 1016 KB Output is correct
8 Correct 12 ms 888 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 13 ms 892 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 14 ms 888 KB Output is correct
8 Correct 11 ms 888 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 13 ms 888 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 396 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 420 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 14 ms 2028 KB Output is correct
12 Correct 15 ms 2204 KB Output is correct
13 Correct 15 ms 1492 KB Output is correct
14 Correct 13 ms 2032 KB Output is correct
15 Correct 22 ms 2404 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 21 ms 2284 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 21 ms 2288 KB Output isn't correct
10 Halted 0 ms 0 KB -