/**
* Author: MatijaL
* Time: 2021-01-17 18:15:39
**/
#include <tickets.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1000000005
#define mod 1000000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;
#define limit 1600
ll median = 0;
struct Card{
ll color, pos;
ll num;
ll worth;
Card(ll a, ll b, ll c){
color = a;
pos = b;
num = c;
worth = abs(num - median);
}
bool operator < (const Card& other){
if(num != other.num) return num < other.num;
if(color != other.color) return color < other.color;
return pos < other.pos;
}
};
bool worth_sort(const Card& a, const Card &b){
if(a.worth!=b.worth) return a.worth > b.worth;
if(a.color!=b.color) return a.color < b.color;
return a.pos < b.pos;
}
ll find_maximum(int K, vector<vector<int>> x){
ll n = x.size();
ll m = x[0].size();
vector<Card> cards[n];
vector<ll> allNumbers;
vector<vector<int>> out(n, vector<int>(m, -1));
loop(i, n)loop(j, m) cards[i].pb(Card(i, j, x[i][j]));
Card medianCard = Card(0,0,0);
vector<Card> allCards;
loop(color, n)loop(j, m) allCards.pb(cards[color][j]);
sort(all(allCards));
medianCard = allCards[(n*m)/2];
median = medianCard.num;
ll preMedian = allCards[(n*m)/2 - 1].num;
bool shiftingEnabled = preMedian == median;
//printf("MEDIAN is %lld %lld\n", median, preMedian);
//porihtaj worth
loop(color, n)loop(j, m) cards[color][j].worth = abs(median - cards[color][j].num);
//1. k najboljsih vsake barve
loop(i, n) sort(all(cards[i]), worth_sort);
vector<Card> left[n];
vector<Card> right[n];
vector<ll> pointL(n, -1);//index zadnjega elementa?????
vector<ll> pointR(n, -1);
//pair<cost, color> right -> subLeft
vector<pll> subLeft;
vector<pll> subRight;
/*
Od vsake barve izberi k najboljsih elementov
Opiši kakšne so cene tega,
da se odpoveš elementu na eni strani za slabši elemnt na drugi
Upoštevaj da lahko element ki je enak mediani uporabiš na obeh straneh!
*/
loop(color, n){
ll cnt = 0;
ll pl = -1;
ll pr = -1;
vector<Card> medianRight;
for(auto e : cards[color]){
//printf("Card %d %d %lld\n", e.color, e.pos, e.worth);
if(cnt < K){
cnt++;
if(e.num == median and shiftingEnabled){
////
left[color].pb(e);
medianRight.pb(e);
//upostevaj samo levega
pointL[color] = left[color].size()-1;
//printf("Median card found\n");
subRight.pb(mp(0, color));
continue;
}
if(e < medianCard) left[color].pb(e);
else right[color].pb(e);
pl = left[color].size()-1;
pr = right[color].size()-1;
pointL[color] = pl;
pointR[color] = pr;
}else{
if(e.num == median and shiftingEnabled){
//poponoma neuporabno
left[color].pb(e);
//probaj dat iz desne
if(pr >= 0) subLeft.pb(mp(right[color][pr].worth - e.worth, color));
pr--;
right[color].pb(e);
//daj z leve
if(pl >= 0) subRight.pb(mp(left[color][pl].worth - e.worth, color));
pl--;
}
else if(e < medianCard){
left[color].pb(e);
//probaj dat iz desne
if(pr >= 0) subLeft.pb(mp(right[color][pr].worth - e.worth, color));
pr--;
}else{
right[color].pb(e);
//daj z leve
if(pl >= 0) subRight.pb(mp(left[color][pl].worth - e.worth, color));
pl--;
}
}
if(pointL[color] > inf) pointL[color] = -1;
if(pointR[color] > inf) pointR[color] = -1;
}
reverse(all(medianRight));
for(auto e : medianRight) right[color].pb(e);
}
/*
printf("Pre-BALANCING\n");
loop(color, n){
printf("Left: ");
loop(i, pointL[color]+1) printf("%lld ", left[color][i].pos);
printf("\n");
printf("Right: ");
loop(i, pointR[color]+1) printf("%lld ", right[color][i].pos);
printf("\n");
}*/
//2. uravnovesi
/*
printf("SUBSTITUTIONS:\n");
printf("Left: ");
for(auto e : subLeft) printf("(%lld %lld) ", e.fs, e.sc);
printf("\n");
printf("Right: ");
for(auto e : subRight) printf("(%lld %lld) ", e.fs, e.sc);
printf("\n");
*/
ll leftCnt = 0;
ll rightCnt = 0;
loop(i, n) leftCnt += pointL[i]+1;
loop(i, n) rightCnt += pointR[i]+1;
//printf("left cnt %d | right cnt %d\n", leftCnt, rightCnt);
sort(all(subLeft));
sort(all(subRight));
for(auto e : subLeft){
if(leftCnt >= rightCnt) break;
//printf("one to the left\n");
ll curColor = e.sc;
if(pointR[curColor] == -1) continue;
leftCnt++;
rightCnt--;
pointL[curColor]++;
pointR[curColor]--;
}
for(auto e : subRight){
if(rightCnt >= leftCnt) break;
//printf("one to the right\n");
ll curColor = e.sc;
if(pointL[curColor] == -1) continue;
rightCnt++;
leftCnt--;
pointR[curColor]++;
pointL[curColor]--;
}
assert(leftCnt == (n*K)/2 and rightCnt == (n*K)/2);
loop(color, n){
assert(pointR[color]+pointL[color]+2 == K);
}
/*
printf("BALANCING\n");
loop(color, n){
printf("Left: ");
loop(i, pointL[color]+1) printf("%lld ", left[color][i].pos);
printf("\n");
printf("Right: ");
loop(i, pointR[color]+1) printf("%lld ", right[color][i].pos);
printf("\n");
}
loop(color, n) printf("%d %d\n", pointL[color]+1, pointR[color]+1);
*/
//printf("here\n");
ll ans = 0;
ll k = 0;
loop(color, n)loop(j, pointL[color]+1){
Card c = left[color][j];
out[c.color][c.pos] = k;
//printf("card %d %d gets %d\n", c.color, c.pos, k);
k++;
k %= K;
ans += c.worth;
}
assert(k == 0);
for(int color = n-1; color >= 0; color--)loop(j, pointR[color]+1){
Card c = right[color][j];
out[c.color][c.pos] = k;
//printf("card %d %d gets %d\n", c.color, c.pos, k);
k++;
k %= K;
ans += c.worth;
}
assert(k==0);
//3 lotimo se dela momci
/*
priority_queue<pll> leftstack;
priority_queue<pll> rightstack;
loop(color, n){
leftstack.push(mp(pointL[color]+1, color));
rightstack.push(mp(pointR[color]+1, color));
}
loop(k, K){
//printf("k = %lld assembly: ", k);
int cl = 0;
int cr = 0;
set<int> usedColors;
int it =0;
//nastimaj leve
while(cl < n/2){
pll e = leftstack.top();
leftstack.pop();
int color = e.sc;
int amnt = e.fs;
it++;
if(it > 10) break;
printf("left color %d -> amnt %d\n", color, amnt);
if(usedColors.count(color) or amnt == 0){
leftstack.push(e);
continue;
};
Card c = left[color][amnt-1];
out[c.color][c.pos] = k;
cl++;
ans += c.worth;
usedColors.insert(color);
leftstack.push(mp(color, amnt-1));
//printf("%lld ", c.num);
}
//pa se desne
while(cr < n/2){
pll e = rightstack.top();
rightstack.pop();
int color = e.sc;
int amnt = e.fs;
it++;
if(it > 10) break;
printf("right color %d -> amnt %d\n", color, amnt);
if(usedColors.count(color) or amnt == 0){
rightstack.push(e);
continue;
};
Card c = right[color][amnt-1];
out[c.color][c.pos] = k;
cr++;
ans += c.worth;
usedColors.insert(color);
rightstack.push(mp(color, amnt-1));
//printf("%lld ", c.num);
}
//printf("\n");
assert(cl == n/2 and cr == n/2);
}*/
allocate_tickets(out);
return ans;
}
