| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1029912 | adaawf | Council (JOI23_council) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
bool a[300005][21];
int c[21], da[21], db[21], z = 0, zz = 0;
int x[300005], y[300005], d[300005];
vector<vector<int>> f, g;
vector<vector<deque<pair<int, int>>>> dd;
priority_queue<pair<long long int, pair<int, int>>> q;
int ch(int x) {
return __builtin_popcount(x);
}
void trans(int x, int y, int z, int t, int w, int l) {
int h = dd[z][t].size();
for (auto w : dd[x][y]) {
dd[z][t].push_back({w.first - l, w.second});
}
pair<int, int> h = {-1, -1}, res = h;
for (auto w : dd[z][t]) {
if (w.first > h.first) h = w;
}
for (auto w : dd[z][t]) {
if (w.first > res.first && w.second != h.second) {
res = w;
}
}
dd[z][t].clear();
dd[z][t].push_back(h);
if (res.first != -1) dd[z][t].push_back(res);
if (dd[z][t].size() != h) q.push({w, {z, t}});
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, l = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
c[j] += a[i][j];
}
}
for (int j = 0; j < m; j++) {
if (c[j] == n / 2) {
da[j] = ++z;
}
else if (c[j] == (n / 2) + 1) {
db[j] = ++zz;
}
else if (c[j] < n / 2) l++;
}
for (int i = 1; i <= n; i++) {
int h = 0, k = 0;
for (int j = 0; j < m; j++) {
if (a[i][j] == 1) {
if (da[j] != 0) {
h += (1 << (da[j] - 1));
}
else if (db[j] != 0) {
k += (1 << (db[j] - 1));
}
}
}
x[i] = (1 << z) - h - 1;
y[i] = (1 << zz) - k - 1;
d[i] = k;
}
g = vector<vector<int>>((1 << z), vector<int>(1 << zz, 0));
dd = vector<vector<deque<pair<int, int>>>>((1 << z), vector<deque<pair<int, int>>>(1 << zz));
for (int i = 1; i <= n; i++) {
dd[x[i]][y[i]].push_back({ch(x[i]) + ch(y[i]), i});
if (dd[x[i]][y[i]].size() > 2) dd[x[i]][y[i]].pop_back();
//cout << i << " " << x[i] << " " << y[i] << " " << d[i] << '\n';
if (dd[x[i]][y[i]].size() == 1) q.push({ch(x[i]) + ch(y[i]), {x[i], y[i]}});
}
while (!q.empty()) {
auto p = q.top();
q.pop();
int x = p.first, u = p.second.first, v = p.second.second;
if (dd[u][v].empty() || g[u][v] == 1) continue;
g[u][v] = 1;
for (int i = 0; i < z; i++) {
if (u & (1 << i)) {
trans(u, v, u - (1 << i), v, x - 1, 1);
}
}
for (int i = 0; i < zz; i++) {
if (v & (1 << i)) {
trans(u, v, u, v - (1 << i), x - 1, 1);
}
}
}
f = vector<vector<int>>((1 << z), vector<int>(1 << zz, -1e9));
for (int i = 0; i < (1 << z); i++) {
for (int j = 0; j < (1 << zz); j++) {
if (g[i][j] == 1) {
f[i][j] = ch(i) + ch(j);
/*for (auto w : dd[i][j]) cout << w.first << "|" << w.second << " ";
cout << '\n';*/
q.push({f[i][j], {i, j}});
}
}
}
while (!q.empty()) {
auto p = q.top();
q.pop();
int x = p.first, u = p.second.first, v = p.second.second;
/*cout << 12131 << " " << u << " " << v << '\n';
for (auto w : dd[u][v]) cout << w.first << "|" << w.second << " ";
cout << '\n';*/
for (int i = 0; i < z; i++) {
if (!(u & (1 << i))) {
trans(u, v, u + (1 << i), v, x, 0);
}
}
for (int i = 0; i < zz; i++) {
if (!(v & (1 << i))) {
trans(u, v, u, v + (1 << i), x, 0);
}
}
}
for (int i = 1; i <= n; i++) {
int h = 0;
for (auto w : dd[x[i]][d[i]]) {
if (w.second != i) {
h = max(h, w.first);
//cout << i << " " << x[i] << " " << d[i] << " " << w.first << " " << w.second << '\n';
}
}
h += ch(y[i]);
cout << m - (z + zz - h) - l << '\n';
}
}