답안 #38730 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38730	2018-01-06T10:45:27 Z	14kg	곤돌라 (IOI14_gondola)	C++11	100 / 100	183 ms	12168 KB

gondola

#include "gondola.h"
#include <map>
#include <set>
#include <algorithm>
#define N 100001
#define MOD 1000000009

using namespace std;
int n, g_num, replace_num[N];
int d_len, d[N];
long long count_tot = 1, multi[100], multi_num[100];
map<int, int> valid_w;
set<int> check;

bool valid_check(int x) {
	set<int>::iterator it = check.lower_bound(x);

	if (it == check.end() || *it != x) return false;
	return true;
}
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_check(in[i])) return 0;
		valid_w[in[i]] = i, check.insert(in[i]);

		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;

	valid(_n, in);
	for (int i = 0; i < n; i++) {
		g_num = g_num == n ? 1 : g_num + 1;
		replace_num[i] = g_num;
	}
	for (int i = 0; i < n; i++) {
		w = replace_num[i];
		while (k <= in[i]) {
			if (valid_w[k] && valid_w[k] != i) {
				out[out_len++] = replace_num[valid_w[k]];
				k++;
			}
			else {
				out[out_len++] = w;
				w = k++;
			}
		}
	} return out_len;
}

long long f(long long x, long long turn) {
	int k = 1;
	long long res = 1;

	multi[0] = 1, multi_num[0] = 0;
	multi[1] = x, multi_num[1] = 1;
	while (multi_num[k] < turn) {
		k++;
		multi[k] = (multi[k - 1] * multi[k - 1]) % MOD;
		multi_num[k] = multi_num[k - 1] * 2;
	}

	for(int i=k; i>=1; i--)
		if (turn >= multi_num[i]) {
			turn -= multi_num[i];
			res = (res*multi[i]) % MOD;
		}
	return res;
}
int countReplacement(int _n, int in[]) {
	if (!valid(_n, in)) return 0;

	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) d[++d_len] = in[i];
	}
	if (d_len == n) count_tot = (long long)n;

	sort(d + 1, d + d_len + 1);

	int k = n + 1;
	for (int i = 1; i <= d_len; i++) {
		count_tot *= f(d_len - i + 1, d[i] - k);
		count_tot %= MOD, k = d[i] + 1;
	} return count_tot;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3324 KB	Output is correct
2	Correct	0 ms	3324 KB	Output is correct
3	Correct	0 ms	3324 KB	Output is correct
4	Correct	0 ms	3324 KB	Output is correct
5	Correct	0 ms	3324 KB	Output is correct
6	Correct	29 ms	6888 KB	Output is correct
7	Correct	13 ms	3324 KB	Output is correct
8	Correct	59 ms	10056 KB	Output is correct
9	Correct	16 ms	5436 KB	Output is correct
10	Correct	66 ms	11112 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3324 KB	Output is correct
2	Correct	0 ms	3324 KB	Output is correct
3	Correct	0 ms	3324 KB	Output is correct
4	Correct	0 ms	3324 KB	Output is correct
5	Correct	0 ms	3324 KB	Output is correct
6	Correct	23 ms	6888 KB	Output is correct
7	Correct	13 ms	3324 KB	Output is correct
8	Correct	63 ms	10056 KB	Output is correct
9	Correct	13 ms	5436 KB	Output is correct
10	Correct	69 ms	11112 KB	Output is correct
11	Correct	0 ms	3324 KB	Output is correct
12	Correct	0 ms	3324 KB	Output is correct
13	Correct	3 ms	3324 KB	Output is correct
14	Correct	0 ms	3324 KB	Output is correct
15	Correct	13 ms	3324 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3324 KB	Output is correct
2	Correct	0 ms	3324 KB	Output is correct
3	Correct	0 ms	3324 KB	Output is correct
4	Correct	0 ms	3324 KB	Output is correct
5	Correct	0 ms	3324 KB	Output is correct
6	Correct	0 ms	3324 KB	Output is correct
7	Correct	0 ms	3456 KB	Output is correct
8	Correct	0 ms	3588 KB	Output is correct
9	Correct	0 ms	3588 KB	Output is correct
10	Correct	0 ms	3588 KB	Output is correct
11	Correct	73 ms	10716 KB	Output is correct
12	Correct	73 ms	11772 KB	Output is correct
13	Correct	66 ms	8472 KB	Output is correct
14	Correct	73 ms	10716 KB	Output is correct
15	Correct	83 ms	12036 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3324 KB	Output is correct
2	Correct	0 ms	3324 KB	Output is correct
3	Correct	0 ms	3324 KB	Output is correct
4	Correct	0 ms	3324 KB	Output is correct
5	Correct	0 ms	3324 KB	Output is correct
6	Correct	0 ms	3324 KB	Output is correct
7	Correct	0 ms	3324 KB	Output is correct
8	Correct	0 ms	3324 KB	Output is correct
9	Correct	123 ms	10188 KB	Output is correct
10	Correct	83 ms	9000 KB	Output is correct
11	Correct	26 ms	5436 KB	Output is correct
12	Correct	39 ms	5964 KB	Output is correct
13	Correct	3 ms	3984 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3324 KB	Output is correct
2	Correct	0 ms	3324 KB	Output is correct
3	Correct	0 ms	3324 KB	Output is correct
4	Correct	0 ms	3324 KB	Output is correct
5	Correct	0 ms	3324 KB	Output is correct
6	Correct	0 ms	3324 KB	Output is correct
7	Correct	0 ms	3324 KB	Output is correct
8	Correct	0 ms	3324 KB	Output is correct
9	Correct	133 ms	10188 KB	Output is correct
10	Correct	99 ms	9000 KB	Output is correct
11	Correct	23 ms	5436 KB	Output is correct
12	Correct	29 ms	5964 KB	Output is correct
13	Correct	6 ms	3984 KB	Output is correct
14	Correct	136 ms	11244 KB	Output is correct
15	Correct	183 ms	12168 KB	Output is correct
16	Correct	19 ms	5040 KB	Output is correct
17	Correct	119 ms	9264 KB	Output is correct
18	Correct	53 ms	6756 KB	Output is correct

답안 #38730

Compilation message