Submission #38715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38715	2018-01-06T10:07:27 Z	14kg	Gondola (IOI14_gondola)	C++11	60 / 100	86 ms	12036 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;
	} return count_tot;
}

Subtask #1
5.0 / 5.0

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	53 ms	10056 KB	Output is correct
9	Correct	13 ms	5436 KB	Output is correct
10	Correct	76 ms	11112 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	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	36 ms	6888 KB	Output is correct
7	Correct	19 ms	3324 KB	Output is correct
8	Correct	53 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	6 ms	3324 KB	Output is correct
14	Correct	0 ms	3324 KB	Output is correct
15	Correct	16 ms	3324 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	69 ms	10716 KB	Output is correct
12	Correct	79 ms	11772 KB	Output is correct
13	Correct	53 ms	8472 KB	Output is correct
14	Correct	86 ms	10716 KB	Output is correct
15	Correct	66 ms	12036 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Memory	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
0 / 15.0

#	Verdict	Memory	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	Incorrect	3324 KB	Output isn't correct
6	Halted	0 KB	-

Subtask #9
0 / 15.0

#	Verdict	Memory	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	Incorrect	3324 KB	Output isn't correct
6	Halted	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Memory	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	Incorrect	3324 KB	Output isn't correct
6	Halted	0 KB	-

Submission #38715

Compilation message