Submission #1029912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1029912	2024-07-21T13:45:59 Z	adaawf	Council (JOI23_council)	C++17	Compilation error	0 ms	0 KB

council

#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';
    }
}

Compilation message

council.cpp: In function 'void trans(int, int, int, int, int, int)':
council.cpp:17:20: error: conflicting declaration 'std::pair<int, int> h'
   17 |     pair<int, int> h = {-1, -1}, res = h;
      |                    ^
council.cpp:13:9: note: previous declaration as 'int h'
   13 |     int h = dd[z][t].size();
      |         ^
council.cpp:17:40: error: conversion from 'int' to non-scalar type 'std::pair<int, int>' requested
   17 |     pair<int, int> h = {-1, -1}, res = h;
      |                                        ^
council.cpp:19:25: error: request for member 'first' in 'h', which is of non-class type 'int'
   19 |         if (w.first > h.first) h = w;
      |                         ^~~~~
council.cpp:19:36: error: cannot convert 'std::pair<int, int>' to 'int' in assignment
   19 |         if (w.first > h.first) h = w;
      |                                    ^
      |                                    |
      |                                    std::pair<int, int>
council.cpp:22:50: error: request for member 'second' in 'h', which is of non-class type 'int'
   22 |         if (w.first > res.first && w.second != h.second) {
      |                                                  ^~~~~~
council.cpp:27:25: error: no matching function for call to 'std::deque<std::pair<int, int> >::push_back(int&)'
   27 |     dd[z][t].push_back(h);
      |                         ^
In file included from /usr/include/c++/10/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
                 from council.cpp:1:
/usr/include/c++/10/bits/stl_deque.h:1493:7: note: candidate: 'void std::deque<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::deque<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1493 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:1493:35: note:   no known conversion for argument 1 from 'int' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1493 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_deque.h:1508:7: note: candidate: 'void std::deque<_Tp, _Alloc>::push_back(std::deque<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::deque<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1508 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:1508:30: note:   no known conversion for argument 1 from 'int' to 'std::deque<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1508 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
council.cpp:29:25: warning: comparison of integer expressions of different signedness: 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if (dd[z][t].size() != h) q.push({w, {z, t}});
      |         ~~~~~~~~~~~~~~~~^~~~