oj.uz

답안 #452035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
452035 2021-08-03T16:24:33 Z rainboy 카니발 티켓 (IOI20_tickets) C++14
53 / 100
 1086 ms 72312 KB 
#include "tickets.h"

using namespace std;

typedef vector<int> vi;

const int N = 1500, M = 1500;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa_[N * M], hh[N * M], ii[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa_[ii[j]] == aa_[i_])
				j++;
			else if (aa_[ii[j]] < aa_[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int ll[N], rr[N], kk[N];

long long find_maximum(int k, std::vector<std::vector<int>> aa) {
	int n = aa.size(), m = aa[0].size();
	vector<vi> ss(n);
	int h, i, j;
	long long ans;

	for (i = 0; i < n; i++) {
		ss[i].resize(m);
		for (j = 0; j < m; j++)
			ss[i][j] = -1;
	}
	ans = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < k; j++) {
			ss[i][k - 1 - j] = 0, ans -= aa[i][k - 1 - j];
			aa_[i * k + j] = aa[i][k - 1 - j] + aa[i][m - 1 - j];
		}
	for (h = 0; h < n * k; h++)
		hh[h] = h;
	sort(hh, 0, n * k);
	for (h = n * k - 1; h >= n * k / 2; h--) {
		i = hh[h] / k, j = hh[h] % k;
		ss[i][k - 1 - j] = -1, ss[i][m - 1 - j] = 1;
		ans += aa_[hh[h]];
	}
	for (i = 0; i < n; i++) {
		ll[i] = 0, rr[i] = m - 1;
		for (j = 0; j < m; j++)
			if (ss[i][j] == 0)
				kk[i]++;
	}
	while (k--) {
		for (i = 0; i < n; i++) {
			aa_[i] = kk[i];
			ii[i] = i;
		}
		sort(ii, 0, n);
		for (i = 0; i < n; i++) {
			int i_ = ii[i];

			if (i < n / 2)
				ss[i_][rr[i_]--] = k;
			else
				ss[i_][ll[i_]++] = k, kk[i_]--;
		}
	}
	allocate_tickets(ss);
	return ans;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 27 ms 2544 KB Output is correct
6 Correct 689 ms 51396 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Incorrect 0 ms 204 KB There is multiple tickets of color 0 on day 0
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 41 ms 3396 KB Output is correct
6 Correct 7 ms 844 KB Output is correct
7 Correct 8 ms 1100 KB Output is correct
8 Correct 1086 ms 72260 KB Output is correct
9 Correct 1020 ms 67292 KB Output is correct
10 Correct 1004 ms 67488 KB Output is correct
11 Correct 1082 ms 72312 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 26 ms 3136 KB Output is correct
14 Correct 27 ms 3184 KB Output is correct
15 Correct 34 ms 3564 KB Output is correct
16 Correct 41 ms 3908 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Incorrect 27 ms 3116 KB There is multiple tickets of color 93 on day 0
21 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 27 ms 2544 KB Output is correct
12 Correct 689 ms 51396 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 288 KB Output is correct
15 Incorrect 0 ms 204 KB There is multiple tickets of color 0 on day 0
16 Halted 0 ms 0 KB -