#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m, K;
vector<int>first, last;
vector<std::vector<int>> answer;
vector<deque<ll>>X;
void use(int color, bool fst, int round){
if(fst){
answer[color][first[color]] = round;
first[color] ++;
X[color].pop_back();
}else{
answer[color][last[color]] = round;
last[color] --;
X[color].pop_front();
}
}
long long find_maximum(int k, std::vector< std::vector<int> > x) {
n = x.size();
m = x[0].size();
K = k;
vector<int>row;
for(int i = 0 ; i < n ; i ++){
first.pb(0);
last.pb(m-1);
}
for(int i = 0 ; i < m ; i ++)row.pb(-1);
for(int i = 0 ; i < n ; i ++)answer.pb(row);
ll ans = 0;
if(m == 1){
for(int r = 0 ; r < k ; r ++){
vector<ll>acum;
for(int i = 0 ; i < n ; i ++){
answer[i][r] = r;
acum.pb(x[i][r]);
}
sort(acum.begin(), acum.end());
for(int i = 0, j = n-1; i < j; i ++, j--){
ans += acum[j] - acum[i];
}
}
allocate_tickets(answer);
return ans;
}else if(m == k){
for(int i = 0 ; i < n ; i ++){
deque<ll>cur;
for(int j = 0 ; j < m ; j ++)cur.push_front(x[i][j]);
X.pb(cur);
}
for(int r = 0 ; r < k ; r ++){
ll ans1 = 0, ans2 = 0;
vector<pair<pair<ll, ll>, ll > > options, options2;
for(int i = 0 ; i < n ; i ++){
options.pb({{X[i].back(), X[i].front()}, i});
options2.pb({{-X[i].front(), -X[i].back()}, i});
}
sort(options.begin(), options.end());
sort(options2.begin(), options2.end());
for(int i = 0 ; i < n/2 ; i ++){
ans1 += abs(options[i].ff.ff - options[i + (n/2)].ff.ss);
//use(options[i].ss, true, r);
//use(options[i + (n/2)].ss, false, r);
options2[i].ff.ff *= -1;
options2[i+(n/2)].ff.ss *= -1;
ans2 += abs(options2[i].ff.ff - options2[i + (n/2)].ff.ss);
}
if(ans1 > ans2){
for(int i = 0 ; i < n/2 ; i ++){
use(options[i].ss, true, r);
use(options[i + (n/2)].ss, false, r);
}
}else{
for(int i = 0 ; i < n/2 ; i ++){
use(options2[i].ss, false, r);
use(options2[i + (n/2)].ss, true, r);
}
}
ans += max(ans1, ans2);
}
allocate_tickets(answer);
return ans;
}
for(int i = 0 ; i < n ; i ++){
deque<ll>cur;
for(int j = 0 ; j < m ; j ++)cur.push_front(x[i][j]);
X.pb(cur);
}
for(int r = 0 ; r < k ; r ++){
vector<ll>acum;
vector<int>v00, v01, v11;
for(int i = 0 ; i < n ; i ++){
if(X[i].back() == 0 and X[i].front() == 0)v00.pb(i);
else if(X[i].back() == 0 and X[i].front() == 1)v01.pb(i);
else v11.pb(i);
}
//cout << "initially 00 = " << v00.size() << " 11 = " << v11.size() << " 01 = " << v01.size() << endl;
int cuenta = min(v00.size(), v11.size());
ans += cuenta;
for(int i = 0 ; i < cuenta ; i ++){
use(v00.back(), true, r);
use(v11.back(), false, r);
v00.pop_back();
v11.pop_back();
}
cuenta = min(max((int)v00.size(), (int)v11.size()), (int)v01.size());
ans += cuenta;
if(v00.size() > v11.size()){
for(int i = 0 ; i < cuenta ; i ++){
use(v00.back(), true, r);
use(v01.back(), false, r);
v00.pop_back();
v01.pop_back();
}
}else if(v00.size() < v11.size()){
for(int i = 0 ; i < cuenta ; i ++){
use(v11.back(), true, r);
use(v01.back(), true, r);
v11.pop_back();
v01.pop_back();
}
}
if(v00.size() == 0 and v11.size() == 0 and v01.size() > 0){
cuenta = v01.size();
ans += cuenta/2;
for(int i = 0 ; i < cuenta ; i += 2){
use(v01.back(), true, r);
v01.pop_back();
use(v01.back(), false, r);
v01.pop_back();
}
}else if(v00.size() > 0){
cuenta = v00.size();
for(int i = 0 ; i < cuenta ; i ++){
use(v00.back(), true, r);
v00.pop_back();
}
}else if(v11.size() > 0 ){
cuenta = v11.size();
for(int i = 0 ; i < cuenta ; i ++){
use(v11.back(), true, r);
v11.pop_back();
}
}
}
allocate_tickets(answer);
return ans;
}
