#include "tickets.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll dp[1507][1507];
ll cnt0[1507];
vector<pair<int, int>>d;
vector<int>os[1507], ls[1507];
int os_[1507], ls_[1507];
vector<vector<int>>ans;
vector<int>ap, am;
bool isap[1507];
bool isam[1507];
bool ismx[1507][1507];
ll mxc[1507];
int mxi[1507], mni[1507];
struct Ket {
int i, j, val;
Ket(int ii, int jj, int vl) {
i = ii;
j = jj;
val = vl;
}
bool operator<(Ket other)const {
return val < other.val;
}
bool operator==(Ket other)const {
return val == other.val;
}
bool operator>(Ket other)const {
return val > other.val;
}
friend ostream& operator<<(ostream& os, Ket val);
};
ostream& operator<<(ostream& os, Ket val) {
os << val.i << " " << val.j << ": " << val.val << "; ";
return os;
}
vector<Ket>sax;
bool give_zero(int i, int r);
bool give_one(int i, int r) {
if (ls_[i] == ls[i].size()) {
give_zero(i, r);
return false;
}
ans[i][ls[i][ls_[i]]] = r;
ls_[i]++;
return true;
}
bool give_zero(int i, int r) {
if (os_[i] == os[i].size()) {
give_one(i, r);
return false;
}
cnt0[i]--;
ans[i][os[i][os_[i]]] = r;
os_[i]++;
return true;
}
void give_max(int i, int r) {
//cout << "-- " << i << " " << r << " " << mxc[i] << endl;
mxc[i]--;
for (int j = mxi[i] + 1; j < n; j++) {
if (ismx[i][j]) {
//cout << j << endl;
mxi[i] = j;
ans[i][j] = r;
break;
}
}
}
void give_min(int i, int r) {
//cout << "== " << i << " " << r << endl;
for (int j = mni[i] + 1; j < n; j++) {
if (!ismx[i][j]) {
mni[i] = j;
////cout << j << " ";
ans[i][j] = r;
break;
}
}
}
ll find_answer(vector<ll>a) {
ll ans = INF;
for (int i = 0; i < a.size(); i++) {
ll cur = 0;
for (int j = 0; j < a.size(); j++) {
cur += abs(a[i] - a[j]);
}
ans = min(ans, cur);
}
return ans;
}
ll find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
if (m == 1) {
vector<ll>v;
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(1, 0);
v.push_back(x[i][0]);
}
allocate_tickets(ans);
return find_answer(v);
}
if (k == 1) {
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j != 0 && j != i) {
dp[i][j] = max(dp[i - 1][j] + mxs[i], dp[i - 1][j - 1] - mns[i]);
}
else if (j == 0) {
dp[i][j] = dp[i - 1][j] + mxs[i];
}
else {
dp[i][j] = dp[i - 1][j - 1] - mns[i];
}
}
}
string s = "";
int j = n / 2;
for (int i = n; i > 0; i--) {
if (j == i || (j != 0 && dp[i - 1][j - 1] - mns[i] == dp[i][j])) {
s += '0';
j--;
}
else {
s += '1';
}
}
reverse(s.begin(), s.end());
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
ans[i][mns_[i]] = 0;
}
else {
ans[i][mxs_[i]] = 0;
}
}
allocate_tickets(ans);
return dp[n][n / 2];
}
if (m == k) {
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
mni[i] = -1;
mxi[i] = -1;
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
Ket ket(i, j, x[i][j]);
sax.push_back(ket);
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
sort(sax.begin(), sax.end());
ll res = 0;
for (int i = 0; i < sax.size() / 2; i++) {
res -= sax[i].val;
}
for (int i = sax.size() / 2; i < sax.size(); i++) {
ismx[sax[i].i][sax[i].j] = true;
//cout << sax[i].i << " " << sax[i].j << endl;
res += sax[i].val;
}
for (int i = 0; i < n; i++) {
bool is_ap = true;
bool is_am = true;
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
is_ap = false;
}
else is_am = false;
}
if (is_am) {
am.push_back(i);
isam[i] = true;
}
else if (is_ap) {
ap.push_back(i);
isap[i] = true;
}
else {
for (int j = 0; j < m; j++) {
if (ismx[i][j]) {
mxc[i]++;
}
}
}
}
//cout << "-> " << ap.size() << " " << am.size() << endl;
////cout << ap[0] << endl;
for (int r = 0; r < k; r++) {
for (int tox : am) {
give_max(tox, r);
}
int cnt = 0;
for (int tox : ap) {
give_min(tox, r);
cnt++;
}
int len = m - r - 1;
for (int tox = 0; tox < n; tox++) {
if (!isap[tox] && !isam[tox]) {
if (cnt < n / 2 && mxc[tox] != 0) {
give_min(tox, r);
if (mxc[tox] == len) {
isap[tox] = true;
am.push_back(tox);
}
cnt++;
}
else {
give_max(tox, r);
if (mxc[tox] == 0) {
isam[tox] = true;
ap.push_back(tox);
}
}
}
}
}
allocate_tickets(ans);
return res;
}
else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cnt0[i] += (x[i][j] == 0);
if (x[i][j] == 0) {
os[i].push_back(j);
}
else {
ls[i].push_back(j);
}
}
}
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
ll res = 0;
for (int r = 0; r < k; r++) {
for (int i = 0; i < n; i++) {
d.push_back({ cnt0[i],i });
}
sort(d.begin(), d.end());
/*for (auto x : d) {
//cout << x.ff << " " << x.ss << " ";
}
//cout << endl;*/
ll cnt = 0;
for (int i = 0; i < n / 2; i++) {
cnt += give_one(d[i].ss, r);
}
for (int i = n / 2; i < n; i++) {
cnt += !give_zero(d[i].ss, r);
}
res += min(cnt, n - cnt);
////cout << res << " ";
d.clear();
}
allocate_tickets(ans);
return res;
}
}
/*
3 1 1 1 2 3
4 4 4 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1
5
*/
