답안 #396783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396783	2021-04-30T18:11:08 Z	peuch	곤돌라 (IOI14_gondola)	C++17	100 / 100	83 ms	6084 KB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;

int valid(int n, int inputSeq[])
{
	int mini = n + 10, id = 0;
	map<int, bool> marc;
	for(int i = 0; i < n; i++){
		if(marc[inputSeq[i]]) return 0;
		if(inputSeq[i] < mini) mini = inputSeq[i], id = i;
		marc[inputSeq[i]] = 1;
	}
	if(mini >= n) return 1;
	for(int i = 0; i < n; i++){
		if(inputSeq[(id + i) % n] <= n && inputSeq[(id + i) % n] != mini) return 0;
		mini++;
		if(mini > n) mini = 1;
	} 
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	map<int, int> ini;
	int mini = 250001, id = 0;
	vector<pair<int, int> > ord;
	for(int i = 0; i < n; i++){
		ord.push_back(make_pair(gondolaSeq[i], i));
		if(gondolaSeq[i] < mini) mini = gondolaSeq[i], id = i;
	}
	
	if(mini > n) mini = 1, id = 0;
	for(int i = 0; i < n; i++){
		ini[(i + id) % n] = mini;
		mini++;
		if(mini > n) mini = 1;
	}
	int cnt = 0;
	int removeNow = n + 1;
	sort(ord.begin(), ord.end());
	for(int i = 0; i < n; i++){
		if(ord[i].first <= n) continue;
		replacementSeq[cnt++] = ini[ord[i].second];
		while(removeNow != ord[i].first)	
			replacementSeq[cnt++] = removeNow++;
		removeNow++;
	}
	return cnt;
}

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

const long long MOD = 1e9 + 9;

long long fexp(long long val, long long a){
	if(a == 0) return 1;
	if(a == 1) return val;
	long long ret = fexp(val, a / 2);
	ret *= ret;
	ret %= MOD;
	if(a % 2 == 1) ret *= val, ret %= MOD;
	return ret;
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n, inputSeq)) return 0;
	
	long long ret = 1;
	long long alive = n;
	int cur = n + 1;
	
	vector<pair<int, int> > ord;
	
	for(int i = 0; i < n; i++)
		ord.push_back(make_pair(inputSeq[i], i));
	
	sort(ord.begin(), ord.end());
	bool flag = true;
	for(int i = 0; i < n; i++){
		if(ord[i].first <= n){
			flag = false;
			alive--;
			continue;
		}
		long long val = ord[i].first - cur;
		ret *= fexp(alive, val);
		ret %= MOD;
		cur = ord[i].first + 1;
		alive--;
	}
	if(flag) ret *= n, ret %= MOD;
	return ret;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	15 ms	2124 KB	Output is correct
7	Correct	11 ms	636 KB	Output is correct
8	Correct	31 ms	3908 KB	Output is correct
9	Correct	9 ms	1356 KB	Output is correct
10	Correct	41 ms	4428 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	19 ms	2124 KB	Output is correct
7	Correct	11 ms	568 KB	Output is correct
8	Correct	31 ms	3900 KB	Output is correct
9	Correct	9 ms	1356 KB	Output is correct
10	Correct	36 ms	4464 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	19 ms	2040 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	48 ms	4604 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	31 ms	4884 KB	Output is correct
12	Correct	36 ms	5476 KB	Output is correct
13	Correct	30 ms	2680 KB	Output is correct
14	Correct	28 ms	4792 KB	Output is correct
15	Correct	29 ms	2844 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	51 ms	4460 KB	Output is correct
10	Correct	47 ms	3760 KB	Output is correct
11	Correct	14 ms	1580 KB	Output is correct
12	Correct	18 ms	1848 KB	Output is correct
13	Correct	4 ms	624 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	49 ms	4376 KB	Output is correct
10	Correct	40 ms	3784 KB	Output is correct
11	Correct	14 ms	1492 KB	Output is correct
12	Correct	19 ms	1872 KB	Output is correct
13	Correct	4 ms	588 KB	Output is correct
14	Correct	63 ms	5316 KB	Output is correct
15	Correct	83 ms	6084 KB	Output is correct
16	Correct	11 ms	1360 KB	Output is correct
17	Correct	44 ms	4036 KB	Output is correct
18	Correct	24 ms	2740 KB	Output is correct

답안 #396783

Compilation message