Submission #336852

#	Time	Username	Problem	Language	Result	Execution time	Memory
336852		chenwz	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	863 ms	76012 KiB

tickets

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include "tickets.h"
using namespace std;
typedef long long LL;
const int maxn = 1505;
typedef vector<int> Ivec;
int n, m;
struct Node {
	LL val;
	int id, col;
	bool operator < (const Node& rhs) const {
		return val > rhs.val;
	}
};
int ansL[maxn], cntR[maxn], pos[maxn];
bool cmp(int a, int b) {return ansL[a] > ansL[b];}
LL find_maximum(int K, vector<Ivec> a){
	priority_queue<Node> q;
	n = a.size(), m = a[0].size();
	for (int i = 0; i < n; ++i) q.push((Node) {a[i][0] + a[i][m - K], 0, i});
	int cnt = n * K / 2;
	for (int i = 1; i <= cnt; ++i)
	{
		Node tp = q.top(); q.pop();
		int id = tp.id + 1, col = tp.col;
		if (id == K) ansL[col] = K;
		else q.push((Node) {a[col][id] + a[col][m - K + id], id, col});
	}
	while (!q.empty()) ansL[q.top().col] = q.top().id, q.pop();
	LL ans = 0;
	vector<Ivec> g(n, Ivec(m, -1));
	for (int i = 0; i < n; ++i) pos[i] = i;
	for (int k = 0; k < K; ++k)
	{
		sort(pos, pos + n, cmp);
//		sort(pos, pos + n, [&](int a, int b) {return ansL[a] > ansL[b];});  //洛谷的交互题评测机不让用lambda表达式……
		for (int i = 0; i < n; ++i)
		{
			int p = pos[i];
			if (i < (n >> 1)) g[p][--ansL[p]] = k, ans -= a[p][ansL[p]];
			else g[p][m - (++cntR[p])] = k, ans += a[p][m - cntR[p]];
		}
	}
	allocate_tickets(g);
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10