oj.uz

Submission #385863

# Submission time Handle Problem Language Result Execution time Memory
385863 2021-04-05T06:53:55 Z alireza_kaviani Gondola (IOI14_gondola) C++11
100 / 100
 35 ms 2400 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

typedef long long ll;

#define X			first
#define Y			second

const int MAXN = 3e5 + 10;
const ll MOD = 1e9 + 9;

ll poww(ll x , ll y){
	ll ans = 1;
	for(; y ; y >>= 1 , x = x * x % MOD)	if(y & 1)	ans = ans * x % MOD;
	return ans;
}

int fact[MAXN] , inv[MAXN] , res[MAXN];

int valid(int n, int inputSeq[]){
	int ind = -1;
	vector<int> vec;
	for(int i = 0 ; i < n ; i++){
		vec.push_back(inputSeq[i]);
		if(inputSeq[i] <= n)	ind = i;
	}
	sort(vec.begin() , vec.end());
	for(int i = 1 ; i < n ; i++){
		if(vec[i] == vec[i - 1])	return 0;
	}
	if(ind == -1){
		for(int i = 0 ; i < n ; i++)	res[i] = i + 1;
		return 1;
	}
	for(int i = 0 ; i < n ; i++){
		res[(ind + i) % n] = inputSeq[ind] + i;
		if(res[(ind + i) % n] > n)	res[(ind + i) % n] -= n;
	}
	for(int i = 0 ; i < n ; i++){
		if(inputSeq[i] <= n && res[i] != inputSeq[i])	return 0;
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	if(valid(n , gondolaSeq) == 0)	return -1;
	vector<pair<int , int>> vec; int len = 0;
	for(int i = 0 ; i < n ; i++){
		if(gondolaSeq[i] > n)	vec.push_back({gondolaSeq[i] , res[i]});
	}
	sort(vec.begin() , vec.end());
	int prv = n;
	for(auto &i : vec){
		replacementSeq[len++] = i.Y;
		for(int j = prv + 1 ; j < i.X ; j++)	replacementSeq[len++] = j;
		prv = i.X;
	}
	return len;
}

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

int countReplacement(int n, int inputSeq[]){
	if(valid(n , inputSeq) == 0)	return 0;
	int k = 0; vector<int> vec;
	for(int i = 0 ; i < n ; i++){
		if(inputSeq[i] > n){
			vec.push_back(inputSeq[i]); k++;
		}
	}
	vec.push_back(n);
	sort(vec.begin() , vec.end());
	ll ans = 1;
	for(int i = 0 ; i < k ; i++){
		ans = ans * poww(k - i , vec[i + 1] - vec[i] - (k < n || i > 0)) % MOD;
	}
	return ans;
}

Subtask #1
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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
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 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 9 ms 896 KB Output is correct
7 Correct 18 ms 1256 KB Output is correct
8 Correct 19 ms 1256 KB Output is correct
9 Correct 6 ms 748 KB Output is correct
10 Correct 27 ms 1380 KB Output is correct

Subtask #3
10.0 / 10.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 2 ms 364 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 12 ms 876 KB Output is correct
7 Correct 22 ms 1276 KB Output is correct
8 Correct 14 ms 1256 KB Output is correct
9 Correct 7 ms 752 KB Output is correct
10 Correct 19 ms 1380 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 9 ms 876 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 20 ms 1508 KB Output is correct

Subtask #4
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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.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 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 380 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct

Subtask #6
20.0 / 20.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 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 15 ms 1380 KB Output is correct
12 Correct 16 ms 1508 KB Output is correct
13 Correct 20 ms 1396 KB Output is correct
14 Correct 14 ms 1380 KB Output is correct
15 Correct 35 ms 2400 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 364 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 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 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
9 Correct 26 ms 1348 KB Output is correct
10 Correct 21 ms 1272 KB Output is correct
11 Correct 10 ms 748 KB Output is correct
12 Correct 11 ms 768 KB Output is correct
13 Correct 4 ms 364 KB Output is correct

Subtask #10
10.0 / 10.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 2 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 24 ms 1348 KB Output is correct
10 Correct 19 ms 1272 KB Output is correct
11 Correct 8 ms 748 KB Output is correct
12 Correct 10 ms 788 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 30 ms 1820 KB Output is correct
15 Correct 33 ms 1904 KB Output is correct
16 Correct 6 ms 676 KB Output is correct
17 Correct 23 ms 1388 KB Output is correct
18 Correct 16 ms 988 KB Output is correct