답안 #38701 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38701	2018-01-06T09:24:02 Z	14kg	곤돌라 (IOI14_gondola)	C++11	90 / 100	19 ms	4236 KB

gondola

#include "gondola.h"
#define MOD 1000000009

int n;
int g_num, valid_w[250001], replace_num[100000];
int out_temp[100000];
long long count_tot = 1;

int valid(int _n, int in[]) {
	bool g_check = false;
	
	n = _n;
	for (int i = 0; i < n; i++) {
		if (g_check) {
			g_num = g_num == n ? 1 : g_num + 1;
		}
		if (valid_w[in[i]]) return 0;
		valid_w[in[i]] = i + 1;

		if (in[i] <= n) {
			if (g_check && g_num != in[i]) return 0;
			else if (!g_check) {
				g_check = true, g_num = in[i];
			}
		}
	}
	return 1;
}

int replacement(int _n, int in[], int out[]) {
	int out_len = 0, w, k = _n + 1;
	long long cnt = 0;

	if (!valid(_n, in)) return -1;

	for (int i = 0; i < n; i++) {
		g_num = g_num == n ? 1 : g_num + 1;
		replace_num[i] = g_num;
		if (in[i] > n) cnt++;
	}

	if (cnt == n) count_tot *= (long long)n;
	for (int i = 0; i < n; i++) {
		w = replace_num[i];
		while (k <= in[i]) {
			if (valid_w[k] && valid_w[k] != i+1) {
				out[out_len++] = replace_num[valid_w[k]-1];
				k++, cnt--;
			}
			else if (valid_w[k]) {
				out[out_len++] = w;
				w = k++, cnt--;
			}
			else {
				out[out_len++] = w;
				w = k++;
				count_tot *= cnt, count_tot %= MOD;
			}
		}
	} return out_len;
}

int countReplacement(int _n, int in[]) {
	if (replacement(_n, in, out_temp) < 0) return 0;
	return (int)count_tot;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #38701

Compilation message