답안 #17249 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17249	2015-11-10T14:47:02 Z	erdemkiraz	곤돌라 (IOI14_gondola)	C++	90 / 100	1000 ms	6924 KB

gondola

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "gondola.h"

int valid(int n, int inputSeq[]) {
	int ind = -1, x = -1;
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] <= n) {
			ind = i;
			x = inputSeq[i];
			break;
		}
	}
	for(int i = ind + 1; i < n; i++) {
		if(inputSeq[i] <= n and (x + i - ind - 1) % n + 1 != inputSeq[i])
			return 0;
	}
	set < int > s;
	for(int i = 0; i < n; i++)
		s.insert(inputSeq[i]);
	return s.size() == n;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int ind = 1;
	for(int i = 0; i < n; i++) {
		if(gondolaSeq[i] <= n) {
			ind = (gondolaSeq[i] - 1 - i + n) % n + 1;
			break;
		}
	}
	vector < ii > v;
	for(int i = 0; i < n; i++) {
		v.push_back(ii(gondolaSeq[i], (ind + i - 1) % n + 1));
	}
	sort(v.begin(), v.end());
	int nxt = n + 1, sz = 0;
	foreach(it, v) {
		int x = it -> first;
		int i = it -> second;
		while(nxt <= x) {
			replacementSeq[sz++] = 	i;
			i = nxt;
			nxt++;
		}
	}
	return sz;
}

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

const int mod = 1e9 + 9;

int countReplacement(int n, int inputSeq[]) {
	if(!valid(n, inputSeq))
		return 0;
	int ans = 1;
	int mx = *max_element(inputSeq, inputSeq + n);
	set < int > s;
	for(int i = 0; i < n; i++)
		if(inputSeq[i] > n)
			s.insert(inputSeq[i]);
	for(int i = n + 1; i <= mx; i++) {
		if(s.count(i)) {
			s.erase(i);
			continue;
		}
		ans = (ll) ans * s.size() % mod;
	}
	if(*min_element(inputSeq, inputSeq + n) > n)
		ans = (ll) ans * n % mod;
	return ans;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3096 KB	Output is correct
2	Correct	3096 KB	Output is correct
3	Correct	3096 KB	Output is correct
4	Correct	3096 KB	Output is correct
5	Correct	3096 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3096 KB	Output is correct
2	Correct	0 ms	3096 KB	Output is correct
3	Correct	0 ms	3096 KB	Output is correct
4	Correct	0 ms	3096 KB	Output is correct
5	Correct	0 ms	3096 KB	Output is correct
6	Correct	16 ms	4812 KB	Output is correct
7	Correct	13 ms	3096 KB	Output is correct
8	Correct	26 ms	6396 KB	Output is correct
9	Correct	4 ms	4152 KB	Output is correct
10	Correct	31 ms	6924 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3096 KB	Output is correct
2	Correct	0 ms	3096 KB	Output is correct
3	Correct	0 ms	3096 KB	Output is correct
4	Correct	0 ms	3096 KB	Output is correct
5	Correct	0 ms	3096 KB	Output is correct
6	Correct	9 ms	4812 KB	Output is correct
7	Correct	10 ms	3096 KB	Output is correct
8	Correct	28 ms	6396 KB	Output is correct
9	Correct	8 ms	4152 KB	Output is correct
10	Correct	31 ms	6924 KB	Output is correct
11	Correct	0 ms	3096 KB	Output is correct
12	Correct	0 ms	3096 KB	Output is correct
13	Correct	0 ms	3096 KB	Output is correct
14	Correct	0 ms	3096 KB	Output is correct
15	Correct	0 ms	3096 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3096 KB	Output is correct
2	Correct	3096 KB	Output is correct
3	Correct	3096 KB	Output is correct
4	Correct	3096 KB	Output is correct
5	Correct	3096 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	3096 KB	Output is correct
2	Correct	3096 KB	Output is correct
3	Correct	3096 KB	Output is correct
4	Correct	3096 KB	Output is correct
5	Correct	3096 KB	Output is correct
6	Correct	3096 KB	Output is correct
7	Correct	3096 KB	Output is correct
8	Correct	3096 KB	Output is correct
9	Correct	3096 KB	Output is correct
10	Correct	3096 KB	Output is correct

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3096 KB	Output is correct
2	Correct	3096 KB	Output is correct
3	Correct	3096 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	메모리	Grader output
1	Correct	3096 KB	Output is correct
2	Correct	3096 KB	Output is correct
3	Correct	3096 KB	Output is correct
4	Correct	3096 KB	Output is correct
5	Correct	3096 KB	Output is correct
6	Correct	3096 KB	Output is correct
7	Correct	3096 KB	Output is correct
8	Correct	3096 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3096 KB	Output is correct
2	Correct	0 ms	3096 KB	Output is correct
3	Correct	0 ms	3096 KB	Output is correct
4	Correct	0 ms	3096 KB	Output is correct
5	Correct	0 ms	3096 KB	Output is correct
6	Correct	0 ms	3096 KB	Output is correct
7	Correct	0 ms	3096 KB	Output is correct
8	Correct	0 ms	3096 KB	Output is correct
9	Correct	66 ms	6528 KB	Output is correct
10	Correct	47 ms	5868 KB	Output is correct
11	Correct	23 ms	4020 KB	Output is correct
12	Correct	23 ms	4284 KB	Output is correct
13	Correct	10 ms	3360 KB	Output is correct

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3096 KB	Output is correct
2	Correct	0 ms	3096 KB	Output is correct
3	Correct	0 ms	3096 KB	Output is correct
4	Correct	0 ms	3096 KB	Output is correct
5	Correct	0 ms	3096 KB	Output is correct
6	Correct	0 ms	3096 KB	Output is correct
7	Correct	0 ms	3096 KB	Output is correct
8	Correct	0 ms	3096 KB	Output is correct
9	Correct	67 ms	6528 KB	Output is correct
10	Correct	52 ms	5868 KB	Output is correct
11	Correct	24 ms	4020 KB	Output is correct
12	Correct	25 ms	4284 KB	Output is correct
13	Correct	9 ms	3360 KB	Output is correct
14	Execution timed out	1000 ms	6920 KB	Program timed out
15	Halted	0 ms	0 KB	-

답안 #17249

Compilation message