답안 #69693 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69693	2018-08-21T11:45:52 Z	E869120	곤돌라 (IOI14_gondola)	C++14	90 / 100	55 ms	7488 KB

gondola

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

int valid(int n, int inputSeq[]) {
	vector<int>vec(250009, 0);
	for (int i = 0; i < n; i++) vec[inputSeq[i]]++;
	for (int i = 0; i <= 250000; i++) { if (vec[i] >= 2) return 0; }

	for (int i = 0; i < n; i++) { if (inputSeq[i] > n) inputSeq[i] = -1; }
	int v = -1;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] != -1) {
			int z = (inputSeq[i] - i + n) % n;
			if (v == -1) v = z;
			else if (v != z) return 0;
		}
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	vector<int>vec(250009, -1);
	int r = -1, maxn = 0;
	for (int i = 0; i < n; i++) {
		maxn = max(maxn, gondolaSeq[i]); vec[gondolaSeq[i]] = i;
		if (gondolaSeq[i] > n) continue;
		if (r == -1) r = (gondolaSeq[i] - i + n) % n;
	}
	if (r == -1) r = 1;
	vector<int>vec2(n, 0); for (int i = 0; i < n; i++) vec2[i] = gondolaSeq[i];
	for (int i = 0; i < n; i++) { gondolaSeq[i] = (r + i) % n; if (gondolaSeq[i] == 0) gondolaSeq[i] = n; }

	int cnt = 0;
	for (int i = n + 1; i <= maxn; i++) {
		if (vec[i] == -1) {
			while (gondolaSeq[cnt] == vec2[cnt]) cnt++;
			replacementSeq[i - n - 1] = gondolaSeq[cnt];
			gondolaSeq[cnt] = i;
		}
		else {
			replacementSeq[i - n - 1] = gondolaSeq[vec[i]];
			gondolaSeq[vec[i]] = i;
		}
	}
	return maxn - n;
}

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

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 31; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

int zz[100009];

int countReplacement(int n, int inputSeq[])
{
	for (int i = 0; i < n; i++) zz[i] = inputSeq[i];
	if (valid(n, zz) == 0) return 0;

	bool OK = false;
	for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) OK = true; }

	long long mod = 1000000009, ret = 1; if (OK == false) ret = n;
	sort(inputSeq, inputSeq + n);
	int cx = n + 1;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] >= cx) {
			ret *= modpow(n - i, inputSeq[i] - cx, mod); ret %= mod; cx = inputSeq[i] + 1;
		}
	}
	return ret;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1480 KB	Output is correct
2	Correct	3 ms	1480 KB	Output is correct
3	Correct	3 ms	1480 KB	Output is correct
4	Correct	3 ms	1480 KB	Output is correct
5	Correct	4 ms	1480 KB	Output is correct
6	Correct	8 ms	1604 KB	Output is correct
7	Correct	16 ms	1868 KB	Output is correct
8	Correct	12 ms	1868 KB	Output is correct
9	Correct	6 ms	1868 KB	Output is correct
10	Correct	15 ms	1872 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1872 KB	Output is correct
2	Correct	3 ms	1872 KB	Output is correct
3	Correct	3 ms	1872 KB	Output is correct
4	Correct	4 ms	1872 KB	Output is correct
5	Correct	4 ms	1872 KB	Output is correct
6	Correct	9 ms	1872 KB	Output is correct
7	Correct	17 ms	1900 KB	Output is correct
8	Correct	13 ms	1900 KB	Output is correct
9	Correct	7 ms	1900 KB	Output is correct
10	Correct	18 ms	1904 KB	Output is correct
11	Correct	4 ms	1904 KB	Output is correct
12	Correct	4 ms	1904 KB	Output is correct
13	Correct	14 ms	1904 KB	Output is correct
14	Correct	3 ms	1904 KB	Output is correct
15	Correct	28 ms	1904 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2492 KB	Output is correct
2	Correct	3 ms	2492 KB	Output is correct
3	Correct	3 ms	2492 KB	Output is correct
4	Correct	4 ms	2492 KB	Output is correct
5	Correct	4 ms	2492 KB	Output is correct
6	Correct	5 ms	2492 KB	Output is correct
7	Correct	3 ms	2492 KB	Output is correct
8	Correct	4 ms	2492 KB	Output is correct
9	Correct	55 ms	2788 KB	Output is correct
10	Correct	43 ms	3028 KB	Output is correct
11	Correct	21 ms	3028 KB	Output is correct
12	Correct	26 ms	3104 KB	Output is correct
13	Correct	9 ms	3104 KB	Output is correct

Subtask #10
0 / 10.0

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

답안 #69693

Compilation message