| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 421750 | idk321 | Carnival Tickets (IOI20_tickets) | C++17 | 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 "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000000LL;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
answer.resize(n, vector<int>(m, -1));
if (m == 1)
{
for (int i = 0; i < n; i++) answer[i][0] = 0;
allocate_tickets(answer);
vector<int> values(n);
for (int i = 0; i < n; i++)
{
values[i] = x[i][0];
}
sort(values.begin(), values.end());
ll res = 0;
int mid = (0 + n - 1) / 2;
for (int i = 0; i < n; i++)
{
res += abs(values[mid] - values[i]);
}
return res;
}
vector<vector<array<int, 2>>> valAndInd(n, vector<array<int, 2>>(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
valAndInd[i][j] = {x[i][j], j};
}
}
for (int i = 0; i < n; i++) sort(valAndInd[i].begin(), valAndInd[i].end());
int big = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) big = max(big, x[i][j]);
}
if (big <= 1)
{
int turn = 0;
array<int, 2> freq = {0, 0};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
freq[x[i][j]]++;
}
}
int res = min({k, freq[0], freq[1]});
vector<int> foundIn(res);
vector<vector<int>> isZero(n);
vector<vector<int>> isOne(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (x[i][j] == 0)
{
isZero[i].push_back(j);
} else
{
isOne[i].push_back(j);
}
}
}
vector<int> good(m);
for (int j = 0; j < m; j++)
{
answer[0][j] = j;
for (int i = 1; i < n; i++)
{
if (x[0][j] == 0)
{
if (!isOne[i].empty())
{
foundIn[j] = i;
answer[i][isOne.back()] = j;
isOne.pop_back();
good[j] = true;
}
} else
{
if (!isZero[i].empty())
{
foundIn[j] = i;
answer[i][isZero.back()] = j;
isZero.pop_back();
good[j] = true;
}
}
}
}
vector<vector<int>> notYet(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (answer[i][j] == -1) notYet[i].push_back(j);
}
}
for (int j = 0; j < m; j++)
{
for (int i = 1; i < n; i++)
{
if (foundIn[j] == i) continue;
answer[i][notYet[i].back()] = j;
notYet[i].pop_back();
}
}
int turnTo = 0;
for (int a = 0; a < m; a++)
{
if (good[a])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (answer[i][j] == a)
{
answer[i][j] = turnTo;
}
}
}
turnTo++;
}
}
for (int a = 0; a < m; a++)
{
if (!good[a])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (answer[i][j] == a)
{
answer[i][j] = turnTo;
}
}
}
turnTo++;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j< m; j++)
{
if (answer[i][j] >= k) answer[i][j] = -1;
}
}
allocate_tickets(answer);
return res;
}
/*
if (k == 1)
{
array<int, 3> best = {-1, -1, -1};
vector<array<int, 2>> byVal;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
byVal.push_back({x[i][j], i});
}
}
sort(byVal.begin(), byVal.end());
vector<array<int, 2>> order;
for (int i = 0; i < n; i++)
{
order.push_back({x[i].front(), i});
}
ll cres = 0;
for (int i = 0; i < n; i++)
{
cres += x[i].back() - byVal[0][0];
}
ll res = INF;
int take = 0;
for (auto val : byVal)
{
int num = val[0];
while (take < n && order[take].front() <= num)
{
cres -=
take++;
}
}
} */
return 1;
}
/*
3 4 3
1 0 1 1
0 1 0 0
0 0 1 1
*/