1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include<algorithm>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#define FOR(i,n) for(int i = 0;i<n;++i)
#define FORI(i,b,n) for(int i = b;i<n;++i)
#define FORD(i,n) for(int i = n;i>=0;--i)
#define ZERO 0.000001
#define MAX ((1<<31)-1)
#define qprintf debug && printf
#define sort2(a,b) if(a>b)swap(a,b);
#define ull long long int
using namespace std;
int debug=1;
#define dcout debug && cout
class A
{
	public:A(){}A(int i,int v):v(v),i(i){}
	int i;
	ull v;
	ull toMedian;
};
struct C
{
	int operator ()(const A a,const A b){
		return a.v<b.v;
	}
};
void f(A*r,ull*d,int k){
	//znajdź maksa w 
	//dla tego i znajdź sortowania, gdzie i nie jest medianą
	//spróbuj zmniejszyć wartość odchylenia wszelkim kosztem
	//zaktualizuj koszta
}
int main(){
	ios_base::sync_with_stdio(0);
	int n,k;
	cin>>n>>k;
	//w tym zadaniu jest kurwa jakiś haczyk, tylko kurwa za chuj nie wiem jaki. Kurwa?!
	//...
	//...dwa dni później:
	//już wiem
	//kurwa...
	if(k==2){
		int*t=new int[n];
		int*t2=new int[n];
		FOR(i,n)cin>>t[i];
		ull totalDiff=0;
		FOR(i,n){
			cin>>t2[i];
			totalDiff+=abs(t[i]-t2[i]);
		}
		totalDiff/=2;
		FOR(i,n){
			if(t[i]==t2[i]){
				cout<<t[i]<<' ';
			}
			if(t[i]<t2[i]){
				ull diff=t2[i]-t[i];
				ull diffToMove = min( diff, totalDiff );
				cout<<t[i]+diffToMove<<' ';
				totalDiff-=diffToMove;
			}
			if(t[i]>t2[i]){
				ull diff=t[i]-t2[i];
				ull diffToMove = min( diff, totalDiff );
				cout<<t[i]-diffToMove<<' ';
				totalDiff-=diffToMove;
			}
		}
	}
	if(k==3){
		int*t1=new int[n];
		int*t2=new int[n];
		int*t3=new int[n];
		FOR(i,n)cin>>t1[i];
		FOR(i,n)cin>>t2[i];
		FOR(i,n)cin>>t3[i];
		//int*offsets=new int[n];
		//FOR(i,n)offsets = min(t1[i], min( t2[i], t3[i] ));
		int*medians=new int[n];
		FOR(i,n)medians[i] = max(min(t1[i],t2[i]), min(max(t1[i],t2[i]),t3[i]));
		//FOR(i,n)cout<<medians[i]<<' ';cout<<endl;return 0;
		ull d1=0,d2=0,d3=0;
		FOR(i,n){
			d1+=abs(medians[i]-t1[i]);
			d2+=abs(medians[i]-t2[i]);
			d3+=abs(medians[i]-t3[i]);
		}
		//pierwszy ma być minimalny
		if(d1>d2){
			swap(d1,d2);
			swap(t1,t2);
		}
		if(d2>d3){
			swap(d2,d3);
			swap(t2,t3);
		}
		if(d1>d2){
			swap(d1,d2);
			swap(t1,t2);
		}
		//trzeci jest największy
		ull diffToreduce = (d3-d2)/2;
		//czyli odejmę diffToreduce od d3, i dodam do d2 i d1 :)
		// i zrobię to tam, dzie d3 nie jest medianą
		FOR(i,n){
			//jeśli d3 jest medianą, to nic nie ugram
			if(medians[i]==t3[i]){
				cout<<t3[i]<<' ';
				continue;
			}
			//czyli jest większa, albo mniejsza
			if(medians[i]<t3[i]){
				//ile mogę przsunąć do góry?
				ull diffToMove = min( (ull)(t3[i]-medians[i]), diffToreduce );
				diffToreduce-=diffToMove;
				cout<<(medians[i]+diffToMove)<<' ';
			}else{
				//ile mogę przsunąć do góry?
				ull diffToMove = min( (ull)medians[i]-t3[i], diffToreduce );
				diffToreduce-=diffToMove;
				cout<<(medians[i]-diffToMove)<<' ';
			}
		}
	}
	if(k==94){
		//ha!
				//a,b,c,d
				//obniż d i c kosztem a i b
				//obniż d i b kosztem c i a
				//obniż d i a kosztem b i c
				//czy to działałoby dla pięciu?
	}
	
	//return 0;
	if(k<4){cout<<"\n";return 0;}
	A**t=new A*[n];
	*t=new A[n*k];
	//wczytaj
	FOR(i,k){
		FOR(j,n){
			if(!i){
				t[j]=*t+j*k;
			}
			cin>>t[j][i].v;
			t[j][i].i=i;
		}
	}

	//pokubełkuj wg sortowań
	C c;
	map<int,A*> m;
	FOR(i,n){
		sort(t[i],t[i]+k,c);
		A*s=t[i];
		int hash=0;
		FOR(j,k){
			hash<<=3;
			hash+=s[j].i;
		}
		if(m.count(hash)){
			FOR(j,k){
				m[hash][j].v+=s[j].v;
			}
		}else
			m[hash]=s;
	}
	//każdy hash to inne sortowanie
	//dane są posortowane wartością, obok jest numer ciągu
	//to wpiszmy ile jest do mediany
	//może najpierw przepisać to do tablicy
	A**r=new A*[m.size()];
	map<int,A*>::iterator it = m.begin();
	map<int,A*>::iterator ite = m.end();
	{
		int i=0;
		for(;it!=ite;++it){
			r[i]=it->second;
			++i;
		}
	}
	int e=m.size();
	int mi=k/2;
	FOR(i, e){
		FOR(j,k){
			r[i][j].toMedian=r[i][mi].v-r[i][j].v;
		}
	}
	//policz odległości do mediany
	ull d[k];
	FOR(i,k)d[i]=0;
	FOR(i,e){
		FOR(j,k){
			d[r[i][j].i]+=abs( r[i][j].v - r[i][mi].v );
		}
	}
	FOR(i,k){
		dcout<<d[i]<<endl;
	}

	//teraz zmniejsz maksa
	//może rekurencyjnie?



	//map<int,map<int,int> > m;//mapa unikalnych sortowań
	//zredukuj o odwrotne sortowania
	//deszyfruj do tablicy[][]

	//i teraz to kurwa przelicz
	//k=5 -> 60, czyli omijając wartości bezwględne 4^60 różnych układów równań po 5 zmiennych + 10 ograniczeń + 4 główne ograniczenia i jedno do maksymalizacji razy 5 możliwych liderów... i to w simplex, po czym wybierz minimum
	//k=4 -> 12 - no ok, ale żeby o trzy punkty tak się jebać..., musi być prostszy sposób
	//k=3 -> 3
	//k=2 -> 1


	return 0;
}