#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> A;
int B[100005]; // B[val] = id
int C[100005];
int D[100005]; // D[id] = sum
int E[100005]; // current
int N, S;
vector<int> DnC2(int s, int e, int a, int b) {
int i, j;
if(s>=e) return {};
if(s+1==e) {
vector<int> v;
for(i=a;i<b;i++) v.push_back(A[s][i]);
v.erase(unique(v.begin(),v.end()),v.end());
return v;
}
int mid = (s+e)/2;
vector<int> v1 = DnC2(s, mid, a, b);
vector<int> v2 = DnC2(mid, e, a, b);
vector<int> v;
v.resize(v1.size()+v2.size());
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v.begin());
v.erase(unique(v.begin(),v.end()),v.end());
return v;
}
void DnC(int s, int e) {
if(e==s+1) return;
int i, j;
vector<int> S = DnC2(0, N, s, e);
int T = S.size();
for(i=0;i<T;i++) B[S[i]] = i;
int mid = (s+e)/2;
for(i=0;i<T;i++) {
D[i] = 0;
}
for(i=0;i<N;i++) {
for(j=s;j<e;j++) {
D[B[A[i][j]]]++;
}
}
vector<int> v;
for(i=0;i<T;i++) {
if(D[i] % 2 == 0) D[i] = 0;
else v.push_back(i);
}
assert(v.size()%2==0);
int sz = v.size();
for(i=0;i<sz/2;i++) D[v[i]] = 1;
for(i=sz/2;i<sz;i++) D[v[i]] = -1;
for(i=0;i<T;i++) E[i] = 0;
for(i=0;i<N;i++) {
vector<array<int, 4>> V;
for(j=s;j<e;) {
int pt = j;
while(pt+1<e&&A[i][j]==A[i][pt+1]) pt++;
//[j ~ pt]
V.push_back({j, pt, A[i][j], -1});
j = pt + 1;
}
vector<array<int, 2>> V2;
for(j=0;j<V.size();j++) {
if((V[j][1]-V[j][0]+1)%2==0) {
V[j][3] = 0;
continue;
}
int n = V[j][2];
V2.push_back({E[B[n]]-D[B[n]], j});
}
sort(V2.begin(),V2.end());
int sz = V2.size();
for(j=0;j<sz/2;j++) V[V2[j][1]][3] = 1;
for(j=sz/2;j<sz;j++) V[V2[j][1]][3] = -1;
int l = s, r = mid;
for(auto n : V) {
int v = n[1] - n[0] + 1;
int a = -1, b = -1;
if(n[3]==0) a = v/2, b=v/2;
if(n[3]==1) a = v/2+1, b = v/2;
if(n[3]==-1) a = v/2, b = v/2+1;
E[B[n[2]]] += n[3];
assert(l+a-1 < mid && r+b-1 < e);
for(j=l;j<=l+a-1;j++) A[i][j] = n[2];
l += a;
for(j=r;j<=r+b-1;j++) A[i][j] = n[2];
r += b;
}
assert(l == mid && r == e);
}
for(i=0;i<T;i++) assert(E[i] == D[i]);
DnC(s, mid);
DnC(mid, e);
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> N >> S >> T;
A.resize(N);
int i, j;
for(i=0;i<N;i++) A[i].resize(S);
for(i=0;i<N;i++) {
for(j=0;j<S;j++) cin >> A[i][j];
}
for(i=0;i<N;i++) sort(A[i].begin(),A[i].end());
DnC(0, S);
for(i=0;i<N;i++) {
for(j=0;j<S;j++)cout << A[i][j] << ' ';
cout << '\n';
}
}
Compilation message
balance.cpp: In function 'std::vector<int> DnC2(int, int, int, int)':
balance.cpp:10:12: warning: unused variable 'j' [-Wunused-variable]
10 | int i, j;
| ^
balance.cpp: In function 'void DnC(int, int)':
balance.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(j=0;j<V.size();j++) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Correct |
| 2 |
Correct |
0 ms |
348 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
0 ms |
348 KB |
Correct |
| 3 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
14640 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
14640 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Correct |
| 2 |
Correct |
0 ms |
348 KB |
Correct |
| 3 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
516 KB |
Correct |
| 2 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
516 KB |
Correct |
| 2 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
516 KB |
Correct |
| 2 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
14640 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
14640 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Correct |
| 2 |
Correct |
0 ms |
348 KB |
Correct |
| 3 |
Correct |
0 ms |
344 KB |
Correct |
| 4 |
Correct |
0 ms |
348 KB |
Correct |
| 5 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
