oj.uz

Submission #285702

# Submission time Handle Problem Language Result Execution time Memory
285702 2020-08-29T12:50:55 Z amoo_safar Gondola (IOI14_gondola) C++17
100 / 100
 36 ms 6520 KB 
#include "gondola.h"

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

int valid(int n, int a[]){
	vector<int> A, S;
	for(int i = 0; i < n; i++) A.pb(a[i]);
	sort(A.begin(), A.end());
	for(int i = 0; i + 1 < n; i++) if(A[i] == A[i + 1]) return 0;
	for(int i = 0; i < n; i++) if(a[i] <= n) S.pb((i - a[i] + n) % n);
	sort(S.begin(), S.end());
	for(int i = 0; i + 1 < (int) S.size(); i++) if(S[i] != S[i + 1]) return 0;
	return 1;
}

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

const int MX = 250010;
int replacement(int n, int a[], int ans[]){
	vector< vector<int> > V(n);

	int L = (*max_element(a, a + n)) - n;
	vector<int> mk(MX, 0);
	int idx = 0;
	for(int i = 0; i < n; i++){
		if(a[i] < n) idx = (i - a[i] + 1 + n) % n;
		mk[a[i]] = 1;
	}
	int mx = max_element(a, a + n) - a;
	for(int i = 1; i <= n; i++) V[(idx + i - 1) % n].pb(i);
	for(int i = n + 1; i <= n + L; i++){
		if(!mk[i])
			V[mx].pb(i);
	}
	for(int i = 0; i < n; i++){
		if(a[i] > n) V[i].pb(a[i]);
	}
	for(int i = 0; i < n; i++)
		for(int j = 1; j < (int) V[i].size(); j++)
			ans[V[i][j] - (n + 1)] = V[i][j - 1];
	return L;
}

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


const int Mod = 1e9 + 9;


int mul(int a, int b){
	return (1ll * a * b) % Mod;
}
int bin_pow(int b, int p){
	int res = 1;
	for(int j = 1, pw = b; j <= p; j <<= 1, pw = mul(pw, pw))
		if(p & j)
			res = mul(res, pw);
	return res;
}

int countReplacement(int n, int a[]){
	if(!valid(n, a)) return 0;
	vector<int> A;
	for(int i = 0; i < n; i++) A.pb(a[i]);
	sort(A.begin(), A.end());
	int res = 1;
	int la = n;
	for(int i = 0; i < n; i++){
		if(A[i] <= n) continue;
		res = (1ll * res * bin_pow(n - i, A[i] - la - 1)) % Mod;
		la = A[i];
	}
	if(n < A[0]){
		res = (1ll * res * n) % Mod;
		return res;
	}
	return res;
}
/*
1
30
16 26 18 19 20 13 22 21 24 25 17 27 28 29 30 1 2 3 11 5 6 8 7 9 10 12 4 23 14 15

3
7
1 2 3 4 5 6 5

7
4
1 2 7 6

4
4
1 2 7 6


*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 10 ms 1020 KB Output is correct
7 Correct 24 ms 1276 KB Output is correct
8 Correct 15 ms 1656 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 21 ms 1784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 10 ms 1020 KB Output is correct
7 Correct 20 ms 1276 KB Output is correct
8 Correct 15 ms 1656 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 21 ms 1784 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 11 ms 896 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 29 ms 1528 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1280 KB Output is correct
2 Correct 1 ms 1280 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1280 KB Output is correct
5 Correct 1 ms 1280 KB Output is correct
6 Correct 1 ms 1280 KB Output is correct
7 Correct 1 ms 1408 KB Output is correct
8 Correct 2 ms 1408 KB Output is correct
9 Correct 2 ms 1408 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 19 ms 5888 KB Output is correct
12 Correct 31 ms 6520 KB Output is correct
13 Correct 21 ms 3964 KB Output is correct
14 Correct 19 ms 5880 KB Output is correct
15 Correct 27 ms 3700 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 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 24 ms 1360 KB Output is correct
10 Correct 20 ms 1088 KB Output is correct
11 Correct 7 ms 680 KB Output is correct
12 Correct 9 ms 660 KB Output is correct
13 Correct 3 ms 384 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 25 ms 1368 KB Output is correct
10 Correct 20 ms 1088 KB Output is correct
11 Correct 8 ms 680 KB Output is correct
12 Correct 9 ms 660 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 36 ms 1448 KB Output is correct
15 Correct 34 ms 1540 KB Output is correct
16 Correct 7 ms 640 KB Output is correct
17 Correct 22 ms 1024 KB Output is correct
18 Correct 13 ms 896 KB Output is correct