oj.uz

Submission #355623

# Submission time Handle Problem Language Result Execution time Memory
355623 2021-01-22T21:14:11 Z Mefarnis Gondola (IOI14_gondola) C++14
100 / 100
 69 ms 6380 KB 
#include <bits/stdc++.h>
#include "gondola.h"
#define maxn 100003
#define maxv 250001
#define mod 1000000009
using namespace std;
typedef long long LL;

int idx[maxv];
int init[maxn];

void calcInit(int n, int inputSeq[], int minIdx) {
	if(minIdx == -1)
		for( int i = 0 ; i < n ; i++ )
			init[i] = i+1;
	else
		for( int i = 0 ; i < n ; i++ ) {
			int d = (i-minIdx+n) % n;
			init[i] = inputSeq[minIdx]+d;
			if(init[i] > n)
				init[i] -= n;
		}
}

int valid(int n, int inputSeq[]) {
	int minIdx = -1;
	set<int> s;
	for( int i = 0 ; i < n ; i++ ) {
		if(s.find(inputSeq[i]) != s.end())
			return 0;
		s.insert(inputSeq[i]);
		if(inputSeq[i] <= n) {
			if(minIdx == -1 || inputSeq[i] < inputSeq[minIdx])
				minIdx = i;
		}
	}
	calcInit(n,inputSeq,minIdx);
	if(minIdx == -1)
		return 1;
	for( int i = 0 ; i < n ; i++ )
		if(inputSeq[i] <= n)
			if(init[i] != inputSeq[i])
				return 0;
	return 1;
}

int replacement(int n, int inputSeq[], int replacementSeq[]) {
	if(!valid(n,inputSeq))
		return 0;
	int maxIdx = -1;
	memset(idx,-1,sizeof(idx));
	for( int i = 0 ; i < n ; i++ ) {
		idx[inputSeq[i]] = i;
		if(maxIdx == -1 || inputSeq[i] > inputSeq[maxIdx])
			maxIdx = i;
	}
	int cnt = 0;
	int curr = init[maxIdx];
	int maxVal = inputSeq[maxIdx];
	for( int i = n+1 ; i <= maxVal ; i++ ) {
		if(idx[i] == -1 || i == maxVal) {
			replacementSeq[cnt++] = curr;
			curr = i;
		}
		else
			replacementSeq[cnt++] = init[idx[i]];
	}
	return cnt;
}

LL calcPow(LL x , int y) {
	if(y == 0)
		return 1;
	LL val = calcPow(x,y/2);
	val = (val*val) % mod;
	if(y & 1)
		val = (val*x) % mod;
	return val;
}

int countReplacement(int n, int inputSeq[]) {
	if(!valid(n,inputSeq))
		return 0;
	sort(inputSeq,inputSeq+n);
	int last = n;
	LL ans = 1;
	for( int i = 0 ; i < n ; i++ )
		if(inputSeq[i] > last) {
			int diff = inputSeq[i]-last-1;
			int base = n-i;
			last = inputSeq[i];
			LL mult = calcPow(base,diff);
			ans = (ans*mult) % mod;
		}
	if(inputSeq[0] > n)
		ans = (ans*n) % mod;
	return (int) ans;
}

/*
int main() {
	int n = 2;
	int inputSeq[n] = {3,4};
	int res = countReplacement(n,inputSeq);
	printf("res = %d\n",res);
	return 0;
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 2412 KB Output is correct
7 Correct 11 ms 748 KB Output is correct
8 Correct 29 ms 4204 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 38 ms 4972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 14 ms 2412 KB Output is correct
7 Correct 13 ms 748 KB Output is correct
8 Correct 29 ms 4204 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 34 ms 4844 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 20 ms 2284 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 48 ms 5100 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1260 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1388 KB Output is correct
8 Correct 2 ms 1388 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct
11 Correct 39 ms 5744 KB Output is correct
12 Correct 39 ms 6252 KB Output is correct
13 Correct 27 ms 3968 KB Output is correct
14 Correct 34 ms 5612 KB Output is correct
15 Correct 29 ms 3948 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 51 ms 4844 KB Output is correct
10 Correct 41 ms 4120 KB Output is correct
11 Correct 15 ms 1644 KB Output is correct
12 Correct 17 ms 2028 KB Output is correct
13 Correct 4 ms 748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 53 ms 4788 KB Output is correct
10 Correct 38 ms 4076 KB Output is correct
11 Correct 14 ms 1644 KB Output is correct
12 Correct 18 ms 2156 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 59 ms 5740 KB Output is correct
15 Correct 69 ms 6380 KB Output is correct
16 Correct 11 ms 1516 KB Output is correct
17 Correct 47 ms 4460 KB Output is correct
18 Correct 24 ms 2668 KB Output is correct