oj.uz

Submission #425123

# Submission time Handle Problem Language Result Execution time Memory
425123 2021-06-12T13:39:37 Z Mlxa Carnival Tickets (IOI20_tickets) C++14
25 / 100
 669 ms 67660 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<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] == 1;
			ones += x[i][j] == 1;
		}
	}
	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]] == 1;
			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]] == 1;
			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 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 292 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 1 ms 204 KB Contestant returned 1936889595 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 30 ms 2864 KB Output is correct
6 Correct 601 ms 62816 KB Output is correct
7 Correct 669 ms 65352 KB Output is correct
8 Correct 4 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 1 ms 204 KB Output is correct
12 Correct 7 ms 972 KB Output is correct
13 Correct 24 ms 2420 KB Output is correct
14 Correct 21 ms 2656 KB Output is correct
15 Correct 662 ms 67660 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.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 1 ms 292 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 1 ms 204 KB Contestant returned 1936889595 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -