답안 #288043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288043	2020-09-01T08:09:21 Z	theStaticMind	곤돌라 (IOI14_gondola)	C++14	100 / 100	66 ms	6008 KB

gondola

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000009
#define mod 998244353
using namespace std;

#include "gondola.h"

int exp(int64_t a, int x){
	if(!x) return 1;
	if(x&1) return a * exp(a, x-1) % modulo;
	int64_t t = exp(a, x/2);
	return t * t % modulo;
}

int valid(int n, int arr[]){
	int x = -1;

	set<int> S;
	for(int i = 0; i < n; i++) S.insert(arr[i]);
	if(sz(S) != n) return 0;

	for(int i = 0; i < n; i++){
		if(arr[i] <= n){
			x = i;
			break;
		}
	}
	if(x == -1) return 1;

	for(int i = 0; i < n; i++){
		if(arr[(x + i) % n] <= n && arr[(x + i) % n] != (arr[x] + i - 1) % n + 1) return 0;
	}
	return 1;

}

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

int replacement(int n, int arr[], int ans[]){
	vector<int> A(n);
	for(int i = 0; i < n; i++) A[i] = arr[i];

	map<int, int> S;
	for(int i = 0; i < n; i++) S[A[i]] = i;

	int x = 0;
	for(int i = 0; i < n; i++){
		if(arr[i] <= n){
			x = i;
			break;
		}
	}
	for(int i = 0; i < n; i++){
		arr[(x + i) % n] = (arr[x] + i - 1) % n + 1;
	}

	int X = max_element(all(A)) - A.begin();

	for(int i = n + 1; i <= A[X]; i++){
		if(S.count(i)) ans[i - n - 1] = arr[S[i]], arr[S[i]] = i;
		else ans[i - n - 1] = arr[X], arr[X] = i;
	}
	return A[X] - n;

}

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

int countReplacement(int n, int arr[]){
	
	if(!valid(n, arr)) return 0;

	int ans = 1;
	vector<int> seq;
	
	for(int i = 0; i < n; i++) if(arr[i] > n) seq.pb(arr[i]);

	if(sz(seq) == n) ans = n;
	
	seq.pb(n);
	sort(all(seq));

	for(int i = 1; i < sz(seq); i++){
		ans = 1ll * ans * exp(sz(seq) - i, seq[i] - seq[i - 1] - 1) % modulo;
	}

	return ans;

}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	13 ms	2432 KB	Output is correct
7	Correct	33 ms	3832 KB	Output is correct
8	Correct	27 ms	4088 KB	Output is correct
9	Correct	8 ms	1664 KB	Output is correct
10	Correct	30 ms	4728 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	14 ms	2304 KB	Output is correct
7	Correct	34 ms	3840 KB	Output is correct
8	Correct	27 ms	4088 KB	Output is correct
9	Correct	8 ms	1536 KB	Output is correct
10	Correct	31 ms	4728 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	17 ms	2176 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	42 ms	4856 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 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	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 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	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	31 ms	4728 KB	Output is correct
12	Correct	36 ms	5368 KB	Output is correct
13	Correct	34 ms	2928 KB	Output is correct
14	Correct	33 ms	4728 KB	Output is correct
15	Correct	35 ms	2336 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	384 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	384 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	44 ms	4224 KB	Output is correct
10	Correct	34 ms	3576 KB	Output is correct
11	Correct	12 ms	1536 KB	Output is correct
12	Correct	16 ms	1792 KB	Output is correct
13	Correct	4 ms	640 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 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	0 ms	384 KB	Output is correct
9	Correct	49 ms	4216 KB	Output is correct
10	Correct	34 ms	3584 KB	Output is correct
11	Correct	13 ms	1536 KB	Output is correct
12	Correct	16 ms	1792 KB	Output is correct
13	Correct	4 ms	640 KB	Output is correct
14	Correct	55 ms	4856 KB	Output is correct
15	Correct	66 ms	6008 KB	Output is correct
16	Correct	10 ms	1408 KB	Output is correct
17	Correct	40 ms	4224 KB	Output is correct
18	Correct	22 ms	2432 KB	Output is correct

답안 #288043

Compilation message