답안 #55588 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55588	2018-07-08T07:32:48 Z	leejseo	곤돌라 (IOI14_gondola)	C++	90 / 100	842 ms	263168 KB

gondola

#include "gondola.h"
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define UNDEF -1

typedef pair<int, int> pii;
long long mod = 1000000009;

int valid(int n, int inputSeq[])
{
	vector<int> L;
	L.resize(n);
	int temp;
	int shift = -1;
	for (int i=0; i<n; i++){
		L[i] = inputSeq[i];
		if (L[i] <= n){
			temp = (i-L[i]+n+1)%n;
			if (shift == UNDEF) shift = temp;
			else if (shift != temp) return 0;
		}
	}
	sort(L.begin(), L.end());
	for (int i=1; i<n; i++) if (L[i-1] == L[i]) return 0;
	L.clear();
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int min_val = 1000000, min_index = -1;
	vector<pii> L;
	for (int i=0; i<n; i++){
		if (min_val > gondolaSeq[i]){
			min_index = i;
			min_val = gondolaSeq[i];
		} 
	}	
	bool b = (min_val > n);	
	for (int j=0; j<n; j++){
			int i = min_index + j;
			int c;
			if (b) c = j;
			else{
				c = (j + min_val)%n;
			}	
			L.push_back(pii(gondolaSeq[i%n], (c == 0 ? n : c)));
	}	
	sort(L.begin(), L.end());	
	int l = 0;
	for (int i=0; i<n; i++){		
		while (L[i].first != L[i].second){
			replacementSeq[l] = L[i].second;
			l++;
			L[i].second = n+l;
		}
	}	
	return l;
}

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

long long llpow(int a, int b){
	if (b == 0) return (long long) 1;
	if (b%2 == 0) return (llpow(a, b/2) * llpow(a, b/2))%mod;
	return (llpow(a, b-1) * a) % mod;
}

int pow(int a, int b){
	return (int) llpow(a, b);
}

int countReplacement(int n, int inputSeq[])
{
  if (!valid(n, inputSeq)) return 0;
	int min_val = 1000000, min_index = -1;
	vector<pii> L;
	for (int i=0; i<n; i++){
		if (min_val > inputSeq[i]){
			min_index = i;
			min_val = inputSeq[i];
		} 
	}	
	bool b = (min_val > n);	
	for (int j=0; j<n; j++){
			int i = min_index + j;
			int c;
			if (b) c = j;
			else{
				c = (j + min_val)%n;
			}	
			L.push_back(pii(inputSeq[i%n], (c == 0 ? n : c)));
	}	
	sort(L.begin(), L.end());	
	long long ans = 1;
	for (int i=0; i<n; i++){
		if (L[i].first == L[i].second) continue;
		if (i == 0) {
			ans = (ans * llpow(n, L[i].first-n-1))%mod;
			ans = (ans * n) %mod;
			continue;
		}
		ans = (ans * llpow(n-i, L[i].first - 1 - max(L[i-1].first, n)))%mod;
	}	
	return (int) ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	480 KB	Output is correct
2	Correct	2 ms	528 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	568 KB	Output is correct
6	Correct	9 ms	868 KB	Output is correct
7	Correct	14 ms	1260 KB	Output is correct
8	Correct	13 ms	1260 KB	Output is correct
9	Correct	7 ms	1260 KB	Output is correct
10	Correct	18 ms	1276 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1276 KB	Output is correct
2	Correct	3 ms	1276 KB	Output is correct
3	Correct	2 ms	1276 KB	Output is correct
4	Correct	2 ms	1276 KB	Output is correct
5	Correct	3 ms	1276 KB	Output is correct
6	Correct	18 ms	1276 KB	Output is correct
7	Correct	16 ms	1276 KB	Output is correct
8	Correct	23 ms	1276 KB	Output is correct
9	Correct	9 ms	1276 KB	Output is correct
10	Correct	21 ms	1276 KB	Output is correct
11	Correct	3 ms	1276 KB	Output is correct
12	Correct	3 ms	1276 KB	Output is correct
13	Correct	8 ms	1276 KB	Output is correct
14	Correct	3 ms	1276 KB	Output is correct
15	Correct	13 ms	1276 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1276 KB	Output is correct
2	Correct	2 ms	1276 KB	Output is correct
3	Correct	2 ms	1276 KB	Output is correct
4	Correct	2 ms	1276 KB	Output is correct
5	Correct	3 ms	1276 KB	Output is correct
6	Correct	3 ms	1276 KB	Output is correct
7	Correct	3 ms	1276 KB	Output is correct
8	Correct	2 ms	1276 KB	Output is correct
9	Correct	5 ms	1276 KB	Output is correct
10	Correct	4 ms	1276 KB	Output is correct
11	Correct	31 ms	2068 KB	Output is correct
12	Correct	34 ms	2068 KB	Output is correct
13	Correct	17 ms	2068 KB	Output is correct
14	Correct	16 ms	2116 KB	Output is correct
15	Correct	33 ms	2488 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2488 KB	Output is correct
2	Correct	2 ms	2488 KB	Output is correct
3	Correct	2 ms	2488 KB	Output is correct
4	Correct	2 ms	2488 KB	Output is correct
5	Correct	2 ms	2488 KB	Output is correct
6	Correct	2 ms	2488 KB	Output is correct
7	Correct	2 ms	2488 KB	Output is correct
8	Correct	3 ms	2488 KB	Output is correct
9	Correct	35 ms	2584 KB	Output is correct
10	Correct	28 ms	2584 KB	Output is correct
11	Correct	13 ms	2584 KB	Output is correct
12	Correct	19 ms	2584 KB	Output is correct
13	Correct	6 ms	2584 KB	Output is correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2584 KB	Output is correct
2	Correct	3 ms	2584 KB	Output is correct
3	Correct	3 ms	2584 KB	Output is correct
4	Correct	3 ms	2584 KB	Output is correct
5	Correct	3 ms	2584 KB	Output is correct
6	Correct	2 ms	2584 KB	Output is correct
7	Correct	2 ms	2584 KB	Output is correct
8	Correct	2 ms	2584 KB	Output is correct
9	Correct	31 ms	3848 KB	Output is correct
10	Correct	26 ms	3848 KB	Output is correct
11	Correct	13 ms	3848 KB	Output is correct
12	Correct	14 ms	3848 KB	Output is correct
13	Correct	6 ms	3848 KB	Output is correct
14	Runtime error	842 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

답안 #55588

Compilation message