oj.uz

Submission #425139

# Submission time Handle Problem Language Result Execution time Memory
425139 2021-06-12T13:54:11 Z Mlxa Carnival Tickets (IOI20_tickets) C++14
39 / 100
 1014 ms 88812 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "tickets.h"
#include <vector>

const int N = 2000;
int cnt[N], lef[N], rig[N];

ll find_maximum(int k, vector<vector<int>> x) {
	int n = (int)x.size();
	int m = (int)x[0].size();
	vector<int> order;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			order.push_back(x[i][j]);
		}
	}
	sort(all(order));
	int bound = -1, best = n * m;
	for (int i = 1; i < (int)order.size(); ++i) {
		if (order[i] == order[i - 1]) {
			continue;
		}
		int val = abs(i - (n * m - i));
		if (best > val) {
			best = val;
			bound = order[i];
		}
	}
	vector<vector<int>> answer(n, vector<int>(m, -1));
	int ones = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cnt[i] += x[i][j] >= bound;
			ones += x[i][j] >= bound;
		}
	}
	fill_n(lef, n, 0);
	fill_n(rig, n, m - 1);

	vector<int> rows(n);
	iota(all(rows), 0);
	for (int i = 0; i < k; ++i) {
		sort(all(rows), [&](int ii, int jj) {
			return cnt[ii] < cnt[jj];
		});
		// cout << "--- " << i << endl;
		for (int j = 0; j < n / 2; ++j) {
			int sj = j;
			j = rows[j];
			// cout << "lef " << j << endl;
			cnt[j] -= x[j][lef[j]] >= bound;
			answer[j][lef[j]++] = i;
			j = sj;
		}
		for (int j = n / 2; j < n; ++j) {
			int sj = j;
			j = rows[j];
			// cout << "rig " << j << endl;
			cnt[j] -= x[j][rig[j]] >= bound;
			answer[j][rig[j]--] = i;
			j = sj;
		}
	}

	vector<vector<int>> res(k);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			// cout << answer[i][j] << " ";
			if (answer[i][j] != -1) {
				res[answer[i][j]].push_back(x[i][j]);
			}
		}
		// cout << endl;
	}
	ll sum = 0;
	for (int i = 0; i < k; ++i) {
		sort(all(res[i]));
		assert((int)res[i].size() == n);
		for (int j = 0; j < n / 2; ++j) {
			sum += res[i][n - 1 - j] - res[i][j];
		}
	}
	allocate_tickets(answer);
	return sum;
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Contestant returned 2146114348 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 460 KB Output is correct
5 Correct 25 ms 2784 KB Output is correct
6 Correct 615 ms 59500 KB Output is correct
7 Correct 634 ms 61640 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 7 ms 972 KB Output is correct
13 Correct 21 ms 2260 KB Output is correct
14 Correct 21 ms 2500 KB Output is correct
15 Correct 657 ms 63604 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory 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 4 ms 588 KB Output is correct
5 Correct 39 ms 3944 KB Output is correct
6 Correct 6 ms 976 KB Output is correct
7 Correct 8 ms 1100 KB Output is correct
8 Correct 1014 ms 88112 KB Output is correct
9 Correct 944 ms 82380 KB Output is correct
10 Correct 962 ms 83616 KB Output is correct
11 Correct 1012 ms 88812 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 460 KB Contestant returned 38977637749 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 460 KB Contestant returned 38977637749 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 0 ms 204 KB Contestant returned 2146114348 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -