| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336851 | chenwz | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
extern "C" void allocate_tickets(std::vector<std::vector<int> > s);
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;
}